Skip to content

Latest commit

 

History

History
123 lines (91 loc) · 4.47 KB

24.1.md

File metadata and controls

123 lines (91 loc) · 4.47 KB
Raw

Exercises 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 π values after each pass. Now, change the weight of edge (z, x) to 4 and run the algorithm again, using s as the source.

Answer

~ s t x y z
d 2 4 6 9 0
π z x y s Ø
~ s t x y z
d 0 0 4 7 -2
π Ø x z s t

but with weight 4 of edge (z, x), BELLMAN-FORD algorithm returns false since there is a negative cycle. To be specific, edge (t, z), (z, x), (x, t) create the negative cycle.

Exercises 24.1-2

Prove Corollary 24.3.

Answer

如果没有通路,则无法进行松弛.

Exercises 24.1-3

Given a weighted, directed graph G = (V, E) with no negative-weight cycles, let m be the maximum over all pairs of vertices u, v ∈ V of the minimum number of edges in a shortest path from u 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.

Answer

We can simply implement this optimization of BELLMAN-FORD algorithm by remebering if v was relaxed or not. If v is relaxed then we wait to see if v was udpated (which means being relaxed again). If v was not updated, then we would stop.

P.S. More explanation:

Because the greatest number of edges on any shortest path from the source is m, then the path-relaxation property tells us that after m iterations of BELLMAN-FORD, every vertex v has achieved its shortest-path weight in v.d. By the upper-bound 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.

Exercises 24.1-4

Modify the Bellman-Ford algorithm so that it sets d[v] to -∞ for all vertices v for which there is a negative-weight cycle on some path from the source to v.

Answer

Bellman-Ford-New(G, w, s)
	Initialize-Single-Source(G, s)
	for i <- 1 to |V[G]| - 1
		do for each edge (u,v) ∈ E[G]
			do Relax[u, v, w]
	for each edge (u, v) ∈ E[G]
		do if d[v] > d[u] + w(u, v)
			d[v] = -∞
	for each v such that d[v] = -∞
		do Follow-And-Mark-Pred(v)

Follow-And-Mark-Pred(v)
	if π[v] != nil and d[π[v]] != -∞
		do d[π[v]] = -∞
		Follow-And-Mark-Pred(π[v])
	else
		return

reference

Exercises 24.1-5 *

Let G = (V, E) be a weighted, directed graph with weight function w : E → R. Give an O(V E)-time algorithm to find, for each vertex v ∈ V , the value δ*(v) = min{u∈V} {δ(u, v)}.

Answer

假设图 G 中没有权值为负的环路.

修改 RELAX 如下:

MOD_RELAX(u, v, w)
    min = w(u, v) + ((u.d < 0) ? u.d : 0)
    if v.d > min
        v.d = min

即更新 v.d 时考虑 u 为源点或者 u 为其他最短路径上某结点这两种情况.

然后运行修改过的 Bellman-Ford 算法:

MOD_BELLMAN_FORD(G, w)
    for each v ∈ G.V
        v.d = Infinity

    for i = 1 to |G.V| - 1
        for each edge(u, v) ∈ G.E
            MOD_RELAX(u, v, w)

最后 v.d 即为所求. 算法的运行时间显然为 O(VE)

Exercises 24.1-6 *

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.

Answer

在 BF 算法找到负权回路上的一个点以后，从该点出发，顺着前驱逆向遍历，即可得到负权回路。

由于是负权回路，所以在 BF 算法的松弛过程中，一定会反复松弛负权回路中的所有边，即在 BF 算法的松弛过程结束后，负权回路中的顶点的前驱也一定是负权回路中的点。

reference

Follow @louis1992 on github to help finish this task.

本节部分答案参考自这里