[Oops.] Counterexample to Bellman-Ford's first attempt at a dynamic programming equation

[alabarre]

Please verify that the error is present in the most recent revision before reporting.

Checked https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf today (24/04/24, or 04/24/24 in the US).

Chapter number or note title: [8. Shortest Paths]

Page number: [294, bottom]

Error description: the triangle u->v->w->u is given as an example where we'd get stuck in an infinite loop, should we attempt to use the identity that precedes it. The argument is that "(...) To compute dist(w) we first need dist(v), and to compute dist(v) we first need dist(u), but to compute dist(u) we first need dist(w).". I disagree with the latter part: if dist(x) is the distance [from some source s] to x, then we are computing the distance [from the source u] to u, which is supposed to be the base case where the identity yields 0.

Suggested fix (if any): If I'm correct and the counterexample is indeed wrong, this one should dispel any doubt: u->v->w->x->v. In this case, to compute dist(x) we first need dist(w), and to compute dist(w) we first need dist(v), but to compute dist(v) we first need dist(x).

[And by the way, thank you so much for making such a wonderful book freely available!]