24.1 The BellmanFord algorithm
24.11
Run the BellmanFord algorithm on the directed graph of Figure 24.4, using vertex $z$ as the source. In each pass, relax edges in the same order as in the figure, and show the $d$ and $\pi$ values after each pass. Now, change the weight of edge $(z, x)$ to $4$ and run the algorithm again, using $s$ as the source.

Using vertex $z$ as the source:

$d$ values:
$$ \begin{array}{cccccc} s & t & x & y & z \\ \hline \infty & \infty & \infty & \infty & 0 \\ 2 & \infty & 7 & \infty & 0 \\ 2 & 5 & 7 & 9 & 0 \\ 2 & 5 & 6 & 9 & 0 \\ 2 & 4 & 6 & 9 & 0 \end{array} $$

$\pi$ values:
$$ \begin{array}{cccccc} s & t & x & y & z \\ \hline \text{NIL} & \text{NIL} & \text{NIL} & \text{NIL} & \text{NIL} \\ z & \text{NIL} & z & \text{NIL} & \text{NIL} \\ z & x & z & s & \text{NIL} \\ z & x & y & s & \text{NIL} \\ z & x & y & s & \text{NIL} \end{array} $$


Changing the weight of edge $(z, x)$ to $4$:

$d$ values:
$$ \begin{array}{cccccc} s & t & x & y & z \\ \hline 0 & \infty & \infty & \infty & \infty \\ 0 & 6 & \infty & 7 & \infty \\ 0 & 6 & 4 & 7 & 2 \\ 0 & 2 & 4 & 7 & 2 \\ 0 & 2 & 4 & 7 & 2 \end{array} $$

$\pi$ values:
$$ \begin{array}{cccccc} s & t & x & y & z \\ \hline \text{NIL} & \text{NIL} & \text{NIL} & \text{NIL} & \text{NIL} \\ \text{NIL} & s & \text{NIL} & s & \text{NIL} \\ \text{NIL} & s & y & s & t \\ \text{NIL} & x & y & s & t \\ \text{NIL} & x & y & s & t \end{array} $$
Consider edge $(z, x)$, it'll return $\text{FALSE}$ since $x.d = 4 > z.d + w(z, x) = 2 + 4$.

24.12
Prove Corollary 24.3.
Suppose there is a path from $s$ to $v$. Then there must be a shortest such path of length $\delta(s, v)$. It must have finite length since it contains at most $V  1$ edges and each edge has finite length. By Lemma 24.2, $v.d = \delta(s, v) < \infty$ upon termination.
On the other hand, suppose $v.d < \infty$ when $\text{BELLMANFORD}$ terminates. Recall that $v.d$ is monotonically decreasing throughout the algorithm, and $\text{RELAX}$ will update $v.d$ only if $u.d + w(u, v) < v.d$ for some $u$ adjacent to $v$. Moreover, we update $v.\pi = u$ at this point, so $v$ has an ancestor in the predecessor subgraph. Since this is a tree rooted at $s$, there must be a path from $s$ to $v$ in this tree. Every edge in the tree is also an edge in $G$, so there is also a path in $G$ from $s$ to $v$.
24.13
Given a weighted, directed graph $G = (V, E)$ with no negativeweight cycles, let $m$ be the maximum over all vertices $v \in V$ of the minimum number of edges in a shortest path from the source $s$ to $v$. (Here, the shortest path is by weight, not the number of edges.) Suggest a simple change to the BellmanFord algorithm that allows it to terminate in $m + 1$ passes, even if $m$ is not known in advance.
If the greatest number of edges on any shortest path from the source is $m$, then the pathrelaxation property tells us that after $m$ iterations of $\text{BELLMANFORD}$, every vertex $v$ has achieved its shortestpath weight in $v.d$. By the upperbound property, after $m$ iterations, no $d$ values will ever change. Therefore, no $d$ values will change in the $(m + 1)$st iteration. Because we do not know $m$ in advance, we cannot make the algorithm iterate exactly $m$ times and then terminate. But if we just make the algorithm stop when nothing changes any more, it will stop after $m + 1$ iterations.
1 2 3 4 5 6 7  BELLMANFORD(M + 1)(G, w, s) INITIALIZESINGLESOURCE(G, s) changes = true while changes == true changes = false for each edge(u, v) ∈ G.E RELAXM(u, v, w) 
1 2 3 4 5  RELAXM(u, v, w) if v.d > u.d + w(u, v) v.d = u.d + w(u, v) v.π = u changes = true 
The test for a negativeweight cycle (based on there being a $d$ value that would change if another relaxation step was done) has been removed above, because this version of the algorithm will never get out of the while loop unless all $d$ values stop changing.
24.14
Modify the BellmanFord algorithm so that it sets $v.d$ to $\infty$ for all vertices $v$ for which there is a negativeweight cycle on some path from the source to $v$.
1 2 3 4 5 6 7 8 9 10 11  BELLMANFORD'(G, w, s) INITIALIZESINGLESOURCE(G, s) for i = 1 to G.V  1 for each edge (u, v) ∈ G.E RELAX(u, v, w) for each edge(u, v) ∈ G.E if v.d > u.d + w(u, v) v.d = ∞ for each vertex v ∈ G.V if v.d = ∞ FOLLOWANDMARKPRED(v) 
1 2 3 4 5 6  FOLLOWANDMARKPRED(v) if v.π != NIL and v.π.d != ∞ v.π.d = ∞ FOLLOWANDMARKPRED(v.π) else return 
24.15 $\star$
Let $G = (V, E)$ be a weighted, directed graph with weight function $w : E \rightarrow \mathbb R$. Give an $O(VE)$time algorithm to find, for each vertex $v \in V$, the value $\delta^*(v) = \min_{u \in V} \{\delta(u, v)\}$.
1 2 3 4  RELAX(u, v, w) if v.d > min(w(u, v), w(u, v) + u.d) v.d = min(w(u, v), w(u, v) + u.d) v.π = u.π 
24.16 $\star$
Suppose that a weighted, directed graph $G = (V, E)$ has a negativeweight cycle. Give an efficient algorithm to list the vertices of one such cycle. Prove that your algorithm is correct.
Based on exercise 24.14, $\text{DFS}$ from a vertex $u$ that $u.d = \infty$, if the weight sum on the search path is negative and the next vertex is $\text{BLACK}$, then the search path forms a negativeweight cycle.