algorithmsearchgraphshortest-pathdijkstra

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.


Solution

  • 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.