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.

(Removed)

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$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)
            v.d = -
    for each vertex v  G.V
        if v.d = -
            FOLLOW-AND-MARK-PRED(v)
1
2
3
4
5
6
FOLLOW-AND-MARK-PRED(v)
    if v.π != NIL and v.π.d != -
        v.π.d = -
        FOLLOW-AND-MARK-PRED(v.π)
    else
        return

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)\}$.

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.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.