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$
  • 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$ – Yuval Filmus Dec 2 '16 at 16:25
  • $\begingroup$ Here's the proof listed serverbob.3x.ro/IA/DDU0150.html As in cormen $\endgroup$ – invartraders 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$ – invartraders Dec 3 '16 at 3:49

Your Answer

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

Browse other questions tagged or ask your own question.