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

C++
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)

C++
DFS-MARK(u)
    if u != NIL and u.d != -∞
        u.d = -∞
        for each v in G.Adj[u]
            DFS-MARK(v)

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

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

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用