[Oops.] Possible mistake lemma 8.3's proof

[jamartinec]

Please verify that the error is present in the most recent revision before reporting. Link: http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE-2up.pdf

Chapter number or note title: [Shortest Paths]

Page number: [286]

Error description: [I think there's no reason to say that there's an edge between the ui and u{i+1} nodes. I

Suggested fix (if any): [ think it would be clearer if two cases were considered: 1) u_{i+1} is a neighbor of ui. In that case dist(u{i+1}) was updated during iteration i, and the relaxation of the arc implies d{i+1}\geq d{i}. 2) u_{i+1} is not a neighbour of ui, so ú{i+1} was already in the priority row before iteration i, and we know then that d_{i+1} \geq d_i.]

Apologies beforehand, if I'm wrong

[jeffgerickson]

You're right, this should be clarified. But I'm consistently using "relaxing an edge" to mean changing the distance at the head, so the proposed fix isn't quite correct either. Even if u_{i+1} is a neighbor of ui, the value of dist(u{i+1}) may not change during iteration i.

[jeffgerickson]

Changed to the following. (I think this is a little clunky, so I may edit further.)