We were given a modification of Fords' algorithm that can detect negative cycles.
Note: $p$ is the predecessor function
Assume that, on the current iteration, arc $wv$ is corrected.
Consider the sequence $S = v, p(v), p(p(v)), . . .$ . Then• either $r$ is the last element of $S$ (and there is no negative cycle so far),
• or $v$ appears in $S$ again (and a negative cycle is found).
THE QUESTION
Show that this modified Fords' algorithm solves the shortest path problem in
finite time by outputting either a negative cycle in $(G,c)$ or a shortest $r − v$ path for each $v ∈ V$ .
FORDS ALGORITHM
We assume that at a certain iteration of the algorithm, a potential $y ∈ \Bbb R^V$ is given together with a map $p : V \setminus\text{{r}} → V$.
Call an arc $vw$ incorrect if $y_w > y_v + c(vw)$.
Ford’s algorithm starts with the potential $y$ and predecessor map $p$ that are given as
$y_r =0$, and $y_v =\infty$, $p(v)=−1$ for every $v∈V$, $v\ne r$.The element $−1$ is chosen arbitrarily. We could use any element or symbol
which does not belong to $V$ . Note also that $p(r)$ is undefined.The algorithm repeats the following basic step: find an incorrect arc $vw$ and correct it by setting
$y_w =y_v +c(vw)$, $p(w)=v$.It stops when all arcs are correct
As with all graph problems, I am not quite sure where to start with this one.
Best Answer
Answering my own question following the posting of solutions...
We only need to show that if $(G, c)$ contains a negative cycle, then the modified algorithm finds it.
We use induction on iteration $q$.
Case $q = 1$ is trivial.
Assume no negative cycle has been found up to (and including) iteration $q − 1$, and on iteration $q$ arc $wv$ was corrected, so $p(v) = w$. On the (backward) path $Q = w,p(w),p(p(w)),...$ there is no repetion (by induction) so its last element is $r$. The path $P = v,p(v),p(p(v)),...$ is the same as the (backward) path $v, w, p(w), p(p(w)), ... $unless $v$ lies on $Q$.
Thus if repetition occurs on $P$, then vertexto be repeated $v$ as $Q$ has no repeated vertices.