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 :)

  • 7
    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 Feb 21, 2014 at 12:48
  • 1
    Does Javascript compile down to actual machine language, or are you getting eaten alive by interpreter overhead? Feb 21, 2014 at 12:49
  • 2
    @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.
    – Jan Hudec
    Feb 21, 2014 at 12:59
  • @JohnR.Strohm You could be right, there will ceratainly be a lot of interpreting going on! Feb 21, 2014 at 13:00

1 Answer 1


Solved problem. I suggest the following references.




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.