1
$\begingroup$

This question is about the correctness proof of Dijkstra's algorithm in the third edition of Introduction to Algorithms by Cormen et al. (pages 660–661).

The proof makes a case that considering path $p$ is the shortest path that connects a vertex in set $S$ (set of vertices where the distance of nodes to node $s$, the starting node, is minimal) to a vertex in set $u$ in $V-S$. It then considers the first vertex as $y$ in set $V-S$ along the path $p$. It argues that $y.d \leq u.d$ which is intuitive as $y$ precedes $u$ in set $V-S$. The second argument that since both $u$ and $y$ were in $V-S$ when $u$ was chosen thus $u.d \leq y.d$. I have following two doubts about the second argument:

  1. Why were $y$ and $u$ both in $V-S$ when $u$ was chosen? We know by our construction that when both $u$ and $y$ are in $V-S$, then $y$ will be chosen before $u$.
  2. The node $u$ is chosen such that when it's added to set $S$ it is not at the minimum distance from node $s$. How is this used in this proof?
$\endgroup$
3
  • 2
    $\begingroup$ It seems that the question will be hard to answer without possession of the (admittedly common) textbook. Perhaps you should ask your TA instead of here. $\endgroup$ Dec 2 '16 at 16:25
  • $\begingroup$ Here's the proof listed serverbob.3x.ro/IA/DDU0150.html As in cormen $\endgroup$ Dec 3 '16 at 3:49
  • $\begingroup$ But because both vertices u and y were in V - S when u was chosen in line 5, we have d[u] ≤ d[y].? How do we know that when both u and y was in set V-S the vertex chosen is u and not y? Where is the fact that node u when added to set S, it is not at the minimum distance from start node s utilized? Please help $\endgroup$ Dec 3 '16 at 3:49
1
$\begingroup$

In answer to both of your questions:

  Firstly, note that during the maintenance phase of the loop invariant proof, we are in the process of inserting u into S, and the way that y is defined is that it is a node in V\S while this is happening, therefore u and y exist in V\S at the same time when u is inserted. This answers your first question.

  Secondly, note that in the proof, we assume that u.dδ(s,u). It therefore follows that there would be a pair of nodes x and y (such that π(y)=x such that x ∈ S and y ∈ V\S) such that y ≠ u and therefore y must come before u, because otherwise from the Convergence Property it would automatically follow that u.d = δ(s,u) which would be a contradiction to our assumption. Therefore from here it must follow that y comes before u. But note that from the first point I made above, y must come after u. And this is exactly the whole point of the proof, both of these things cannot happen simultaneously unless y.d = δ(s,y) = δ(s,u) = u.d.

Note that we used the assumption that u is not the minimal distance from s when added to S by showing that we reach a contradiction if we assume this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.