[yumario]

I believe A* should always give the minimum path as long the heuristic is optimistic. It will become a greedy search if the heuristic is pessimistic. If the heuristic is "perfect" i.e heuristic(x to y) = min_cost(x to y) the the search will be optimal (i.e no nodes that do not belong with the path will be explored)

Yep after playing around with it for a bit it didn't give a minimum path. I believe something is wrong with the heuristic you are using.

Edit: You can prove A* will give a min path as long as: heuristic(x to y) <= min_cost(x to y). Problem seems to be here https://github.com/ssaric/algoviz/blob/master/src/util/GridN... I think it should be a matter of removing "times 100"

[forsythe]

I believe the push and pull is between optimal path and time to find the path. The heuristic dictates whether the algorithm will lean towards Dijkstra or Greedy or somewhere in between.

I got my knowledge about heuristics from here:

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics...

[nemetroid]

Whether a greedy heuristic is faster or not is dependent on the structure of the graph. For the example in the article about mountains and grassland, it makes sense that such a heuristic would speed up the search, since the algorithm can't get stuck in dead-ends.

But in a problem where the algorithm can get stuck in dead-ends, it's possible to construct examples where the greedy heuristic is (much) slower than plain Manhattan distance. Here's an example:

                xxx
                xEx
                x x
                x x
                x x
                x x
  Sxxxxxxxxxxxxxx x
                  x
   xxxxxxxxxxxxxxxx