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.

Is this the exact question? If not can you please post it exactly, word for word? — IVlad, Sep 18 '10 at 23:02
My only guess is to use zero-weight edges (since they're explicitly allowed in ITA). Obviously, in network of zero-edges every path - shortest. — Nikita Rybak, Sep 19 '10 at 01:10

score 12 · Answer 1 · answered Mar 04 '13 at 11:22

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

It seems the only case is some edge has a weight of zero. In this example, the D and C has a same value 1 after (A, B) is relaxed. If D is picked before C, the (C, D) relax will not be evaluated. — jason zhang, Dec 20 '15 at 05:31

score 4 · Accepted Answer · edited Oct 04 '15 at 19:27

4

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.

edited Oct 04 '15 at 19:27

raghavsood33

749
7
17

answered Nov 10 '11 at 04:49

Nate

2,205
17
21

I don't know if it's right, but I marked your answer as the solution. – Steinbitglis Dec 01 '11 at 23:34
1

@Nate your argument- "...algorithm only relaxes edges to vertices that it does not already know the shortest path to" is incorrect. Whenever a vertex is added, Dijkstra rather relaxes each outgoing edge – raghavsood33 Oct 04 '15 at 18:45
@raghavsood33 That sounds correct; Dijkstra relaxes every outgoing edge when it visits a node. I like user2131509's answer. – Nate Oct 05 '15 at 21:59

score 2 · Answer 3 · answered Sep 30 '10 at 02:14

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.

score 1 · Answer 4 · answered Nov 26 '13 at 06:38

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

score 0 · Answer 5 · answered Sep 19 '10 at 03:38

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.

The edges of the shortest path is still relaxed in order, aren't they? — Steinbitglis, Sep 19 '10 at 08:30

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

5 Answers5