Programming conundrum - most efficient path

Question

I have a non-language-specific problem which I'm having trouble finding a workable answer for.

I have a 10x10 grid containing integer values from 1-10. Each value represents the cost of travelling across that square, moving north, east, south or west (cost is incurred while stepping off a square rather than onto it).

I need to find a method to navigate the cheapest path from a starting square to an end point.

I was using a recursive javascript function whereby each square could ask an adjacent square what the cost was if the journey went that way; the square asked would then ask its neighbours etc. until the cheapest route was found. However, as might be expected this takes far too long, even if each square was marked as busy so it couldn't be asked again (in order to prevent circular routes which might never end).

I'm sure this must have been done before. Does anyone have a method they feel would work?

Thanks for your help :)

• ratchet freak: it's called path finding, your solution looks like a floodfill starting from the destination, best solution (given good hueristic) is A* otherwise look up dijkstra's algorithm
• John R. Strohm: Does Javascript compile down to actual machine language, or are you getting eaten alive by interpreter overhead?
• Jan Hudec: @JohnR.Strohm: He's getting eaten alive by the complexity. Recursive function asking it's neighbours is clearly a brute-force and O(2^n) is not going to fly even for |V|=100.
• CompanyDroneFromSector7G: @JohnR.Strohm You could be right, there will ceratainly be a lot of interpreting going on!

Answer 1

Solved problem. I suggest the following references.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

http://en.wikipedia.org/wiki/A*_search_algorithm

https://github.com/bgrins/javascript-astar