CODEWITHSUNDEEP
javaalgorithma-star
harrythomas
harrythomas

Reputation: 1467

Does A* always provide shortest path?

I am trying to understand how A*, Uniform cost and greedy search algorithms work. I know that the way in which nodes are explored changes in all 3 algorithms (greedy will explore based on heuristic value, A* based on heuristic plus distance, uniform based on distance).

I want to know if for a given source and destination should all 3 algorithms provide the shortest path (with just a different number of cities explored?) or can they provide a different path.

I am mostly confused due to the implementation part of - if you store nodes in queue then when you are about to explore the destination node you will have the shortest path for it but if you have queue of paths (and this queue is now sorted based on heuristic + distance) then you might not always get the shortest path.

Upvotes: 2

Views: 5096

Answers (2)

Nensi601
Nensi601

Reputation: 136

In fact the heuristic should be admissible otherwise A* will find a suboptimal solution. I think the queue should not be ordinated by the distance of the next node but using the heuristic that will put as next node the most promising one. Think it as: the next node may be the most distant from the current one but at the same time it can be the nearest one to the destination.

Upvotes: 1

orlp
orlp

Reputation: 117801

Not necessarily, it depends on your heuristic. See this section in Wikipedia that explains it in detail.

To summarize, A* gives an optimal solution if the heuristic is admissable (meaning it never overestimates the cost).

Upvotes: 5

Related Questions