CODEWITHSUNDEEP
algorithmsearchgraphshortest-pathdijkstra
Steve
Steve

Reputation: 87

In Dijkstra's algorithm why must it first expand nodes with the current least cost?

I have read in other posts that Dijkstra's algorithm always expands the shortest path first. Why must it be implemented in such a way? Say we created a relaxed version of Dijkstra's that expands any unvisited paths/nodes as long as they have a cost (calculated on the previous iteration) that's less than infinity.

I have worked through some examples and have yet to show an example that fails to calculate the correct shortest path using this relaxed version of the algorithm.

Upvotes: 1

Views: 755

Answers (2)

cbreezier
cbreezier

Reputation: 1312

The key concept in Dijkstra's algorithm is that once you visit a node, you never have to visit it again. This is because we always explore the cheapest path first, so the first time we arrive at a node is guaranteed to be the cheapest way to get there.

It's also why we must explore the cheapest path first, and why negative weights (which destroy our assumption) invalidate Dijkstra's algorithm.

Upvotes: 0

Aldinjo
Aldinjo

Reputation: 432

If you expand any node, you would eventually find some path to the goal but you cannot guarantee that the path cost to the goal is optimal.

If you find a cheaper path to an already visited node, you would have to update all nodes from this visited node transitively, rendering your relaxed algorithm less efficient than the original one.

Upvotes: 4

Related Questions