Does dijkstras algorithm relax the edges of the shortest path in order?

Question

In "Introduction to algorithms, 3rd edition" exercise 24.3-5 wants an example that this is wrong (not always true). Is that possible? In my mind this is impossible because every edge is relaxed at a time when the path to the current vertice is already decided.

Word for word:

Professor N. claims to have a proof of correctness of Dijkstra's algorithm. He claims that Dijkstra's algorithm relaxes the edges of every shortest path in the graph in the order in which they appear on the path, and therefore the path-relaxation property applies to every vertex reachable from the source. Show the professor is mistaken by constructing a directed graph for which Dijkstra's algorithm could relax the edges of a shortest path out of order.

Answer 1

I think the key phrase in the wording is that dijkstra's algorithm "relaxes the edges of every shortest path in the graph..."

That alone is a lie if there are multiple shortest paths of the same cost.

Consider this graph: A -> B, A -> C, B -> D, C -> D. Source is A and Destination is D. Every edge weight is 1. There are two paths from A to D, one through B and one through C. However one edge B->D or C->D never gets relaxed.

Still not convinced because dijkstra terminates before evaluating the other edge into D? Toss in an extra edge D->E and set the Destination to E. The path from A->D through B is the same cost as A->D through C and they are both cheaper than the cost from A->E. However you will never relax the second edge into D since the algorithm only relaxes edges to vertices that it does not already know the shortest path to.

Answer 2

Consider the following directed graph :(A,B),(A,C),(B,D),(C,D), (D,E)with edge weights w(A,B)=1,w(A,C)=1,w(B,D)=0,w(C,D)=0, w(D,E)=1.The source vertex is A. A possible permutation of edges relaxed in the Dijkstra’s algorithm is (A,B), (A,C), (B,D), (D,E), (C,D). Besides, A.d=0, B.d=1, C.d=1, D.d=1, E.d=2 after performing the Dijkstra’s algorithm. There are two shortest paths from A to E, one is ABDE, and the other is ACDE. The contradiction is to the second path, edge (C,D) should be always relaxed before (D,E).

Answer 3

The point is that the conclusion doesn't follow from the premises, and to construct a counterexample. SSSP finds all shortest paths. There is no reason that shortest-paths need be found in strict order. Consider a tree-graph. All paths are also shortest. Now, if we relax the root, then there is no particular ordering on the edges. But suppose you even imposed one. Then after relaxing the closest non-root node, you might have a bunch of really long edges to the second tier. The next closest root-neighbor might have a bunch of really short outbound edges to that portion of the second tier. In that case, you'll relax edges that contribute to a total path length SHORTER than other edges you'd already relaxed, since you always relax NODES, not edges, in shortest-path order.

Answer 4

Consider the graph:

    A--->B  A--->C  B--->C  C--->D 

and let every edge have weight 0.

Dijkstra's algorithms could relax the edges in the order

    (A,C) (A,B) (C,D) (B,C)

The graph has two shortest paths from A to D, both costing 0.

    A-->B-->C-->D   or   A-->C-->D

The edges of the shortest path {A-->B-->C-->D} are relaxed out of order as (B,C) is relaxed AFTER (C,D).

Answer 5

Produce a single edge, weight three, that reaches the destination. Now add a path consisting of several stops, total weight less than three, that also reach the destination. When you relax the origin, you'll color the destination node as three, which is wrong. You have to continue relaxing all nodes closer than (min known path to destination) until that set is empty. Only then can you be sure D's algorithm has given you the correct answer.

Look up A* algorithm for more fun.