24.1 The Bellman-Ford algorithm
24.1-1
Run the Bellman-Ford 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.1-2
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{BELLMAN-FORD}$ 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.1-3
Given a weighted, directed graph $G = (V, E)$ with no negative-weight 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 Bellman-Ford algorithm that allows it to terminate in $m + 1$ passes, even if $m$ is not known in advance.
By the upper bound theory, we know that after $m$ iterations, no $d$ values will ever change. Therefore, no $d$ values will change in the $(m + 1)$-th iteration. However, we do not know the exact $m$ value in advance, we cannot make the algorithm iterate exactly $m$ times and then terminate. If we try to make the algorithm stop when every $d$ values do not change anymore, then it will stop after $m + 1$ iterations.
24.1-4
Modify the Bellman-Ford algorithm so that it sets $v.d$ to $-\infty$ for all vertices $v$ for which there is a negative-weight cycle on some path from the source to $v$.
BELLMAN-FORD'(G, w, s)
INITIALIZE-SINGLE-SOURCE(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)
mark v
for each vertex u ∈ marked vertices
DFS-MARK(u)
After running $\text{BELLMAN-FORD}'$, run $\text{DFS}$ with all vertices on negative-weight cycles as source vertices. All the vertices that can be reached from these vertices should have their $d$ attributes set to $-\infty$.
24.1-5 $\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)\}$.
24.1-6 $\star$
Suppose that a weighted, directed graph $G = (V, E)$ has a negative-weight cycle. Give an efficient algorithm to list the vertices of one such cycle. Prove that your algorithm is correct.
Based on exercise 24.1-4, $\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 negative-weight cycle.