I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more vertices than Dijkstra's algorithm. What I'm asking however is the following. Given an A star algorithm with some heuristic which is not the heuristic returning 0, could it possibly check more vertices than Dijkstra's algorithm?

My intuition is yes, and I will show why. Consider the Figure underneath, in which we consider a large amount of discrete points in this plane, representing the vertices of the graph, and connecting arcs with cost 1 between all adjacent points, creating a grid graph. Suppose the heuristic used by A star is euclidean distance, and suppose many curved walls like the ones I drew in the middle exist in this fashion, not only the three I drew. A star in this situation would be "tricked" to go in between the walls, since the heuristic would guide it close to the point, only to find out it's a dead end (or a local optimum of some sorts if you will), and this would happen as many times as there are walls. Dijkstra would not be tricked this way. The only problem with my example here, is that Dijkstra will probably not outperform A star here. So, is my intuition wrong, or do more clever instances than this one exist in which Dijkstra can in fact outperform A star in terms of vertices checked?

enter image description here


2 Answers 2



Dijkstra will explore all nodes with cost less than the cost of the completed path. While A* will explore all nodes with cost+heuristic less than the cost of the completed path.

Thus if the heuristic is always positive then A* will expand less or equal nodes.


I don't see why not. A* is heuristic based, if your heuristic is completely wrong the algorithm can end up preferring the search in a wrong direction in the solutions space. You could even design a heuristic that only ever brings the algorithm to a place in the solutions space without ever bringing it closer to the actual goal.

I don't see how this algorithm, which is quite literally heuristics-based Dijkstra, has any mathematical limitation in terms of how much worse it can be than Dijkstra.


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.