CLRS24 单源最短路径

2017-05-30 | 阅读：次

介绍

广度优先搜索算法就是一个求取最短路径的算法，但该算法只能用于无权重的图。
在已知算法中，单结点对最短路径问题最坏情况下渐进运行时间和单源最短路径算法一样。
最短路径具有最优子结构：两个结点之间的一条最短路径包含其他的最短路径。
Dijkstra算法就是一个贪心算法，而Floyd-Warshall算法是一个动态规划算法(该算法能找出所有结点对之间的最短路径)。
如果有权重为负值的环路，则单源最短路径无定义(-INFINITE)。
最短路径不包括环路。至多只包含 V -1条边。
松弛操作

INITIALIZE-SINGLE-SOURCE(G, s)
    for each vertex v in G.V
        v.d = INFINITE
        v.pai = NIL
    s.d = 0

RELAX(u, v, w)
    if v.d > u.d + w(u, v)
        v.d = u.d + w(u, v)
        v.pai = u

Dijkstra算法对每条边松弛一次，Bellman-Ford算法对每条边松弛 V -1次。

24.1 Bellman-Ford算法

边的权重可以为负值。可以判断是否有权重为负值的环路。

BELLMAN-FORD(G, w, s)
    INITIALIZE-SINGLE-SOURCE(G, s)
    for i = 1 to |G.V| - 1
        for each edge (u, v) in G.E
            RELAX(u, v, w)
    for each edge (u, v) in G.E
        if v.d > u.d + w(u, v)
            return FALSE
    return TRUE

运行时间为O(VE)

可以用松弛性质来证明正确性。且如果图G不包含从源结点s可以到达的权重为负值的环路，则Bellman-Ford算法返回TRUE，否则返回FALSE.
练习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.

~   s   t   x   y   z
d   2   5   6   9   0
π   z   s   z   s   Ø

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

练习24.1-2 Prove Corollary 24.3.

如果无法到达，则无法松弛。

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

如果某次循环中没有结点的值被更新，则结束。

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

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

练习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)}.

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

MOD_BELLMAN_FORD(G, W)
    for each v in G.V
        v.d = INFINITY
    for i = 1 to |G.V| - 1
        for each edge(u, v) in G.E
            MOD_RELAX(u, v, w)

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

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

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

有向无环图中的单源最短路径问题

只需按照拓扑次序对结点进行一边处理即可，运行时间是$\Theta(V + E)$

DAG-SHORTEST-PATHS(G, w, s)
    topologically sort the vertices of G
    INITIALIZE-SINGLE-SOURCE(G, s)
    for each vertex u, taken in topologically sorted order
        for each vertex v in G.Adj[u]
            RELAX(u, v, w)

练习24.2-1 Run DAG-SHORTEST-PATHS on the directed graph of Figure 24.5, using vertex r as the source.

It's easy.

练习24.2-2 Suppose we change line 3 of DAG-SHORTEST-PATHS to read 3 for the first

- 1 vertices, taken in topologically sorted order Show that the procedure would remain correct.

最后一个节点没有出边。

练习24.2-3 The PERT chart formulation given above is somewhat unnatural. It would be more natural for vertices to represent jobs and edges to represent sequencing constraints; that is, edge (u, v) would indicate that job u must be performed before job v. Weights would then be assigned to vertices, not edges. Modify the DAG-SHORTEST-PATHS procedure so that it finds a longest path in a directed acyclic graph with weighted vertices in linear time.

PERT(G)
    topologically sort the vertices of G
    INITIALIZE(G)
    for each vertex u, taken in topologically sorted order
        for each vertex v in G.Adj[u]
            RELAX(u, v)

INITIALIZE(G)
    for each vertex v in G.V
        v.d = v.w
        v.pai = nIL

RELAX(u, v)
    if v.d < u.d + v.w
        v.d = u.d + v.w
        v.pai = u

练习24.2-4 Give an efficient algorithm to count the total number of paths in a directed acyclic graph. Analyze your algorithm.

DAG-PATHS(G, s)
    topologically sort the vertices of G
    INITIALIZE(G, s)
    for each vertex u, taken in topologically sorted order
        for each vertex v in G.Adj[u]
            c[v] += c[u]

INITIALIZE(G, s)
    for each vertex v in G.V
        c[v] = 0
    c[s] = 1

Dijkstra算法

Dijkstra算法解决的是带权重的有向图上单源最短路径问题，要求所有边权重都非负。

DIJKSTRA(G, w, s)
    INITIALIZE-SINGLE-SOURC(G, s)
    S = {}
    Q = G.V
    while Q is not empty
        u = EXTRACT-MIN(Q)
        S = S U {u}
        for each veretx v in G.Adj[u]
            RELAX(u, v, w)

Dijkstra算法使用了贪心策略。
若优先队列使用斐波那契堆实现，运行时间为 O(VlgV + E)
练习24.3-1 Run Dijkstra’s algorithm on the directed graph of Figure 24.2, first using vertex s as the source and then using vertex z as the source. In the style of Figure 24.6, show the d and π values and the vertices in set S after each iteration of the while loop.

Just follow the algorithm.

练习24.3-2 Give a simple example of a directed graph with negative-weight edges for which Dijkstra’s algorithm produces incorrect answers. Why doesn’t the proof of Theorem 24.6 go through when negative-weight edges are allowed?

很容易找反例。

练习24.3-3 Suppose we change line 4 of Dijkstra’s algorithm to the following. 4 while

> 1. This change causes the while loop to execute

- 1 times instead of

times. Is this proposed algorithm correct?

正确，其它点已经relax过，不可能再更新。

练习24.3-4 Gaedel教授

for each vertex v in G.V
    for each edge e in G.Adj[v]
        see if the other end of edge can be updated

练习24.3-5 Newman教授

举反例即可。

练习24.3-6 We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated value r(u, v), which is a real number in the range 0 ≤ r(u, v) ≤ 1 that represents the reliability of a communication channel from vertex u to vertex v. We interpret r(u, v) as the probability that the channel from u to v will not fail, and we assume that these probabilities are independent. Give an efficient algorithm to find the most reliable path between two given vertices.

直接运行Dijkstra算法就行了。

练习24.3-7 Let G = (V, E) be a weighted, directed graph with weight function w : E → {1, 2, …, W } for some positive integer W , and assume that no two vertices have the same shortest-path weights from source vertex s. Now suppose that we define an unweighted, directed graph G’ = (V U V’, E’) by replacing each edge (u, v) ∈ E with w(u, v) unit-weight edges in series. How many vertices does G’ have? Now suppose that we run a breadth-first search on G’. Show that the order in which vertices in V are colored black in the breadth-first search of G’ is the same as the order in which the vertices of V are extracted from the priority queue in line 5 of DIJKSTRA when run on G.

反正找出的都是单源最短路径。

练习24.3-8 Let G = (V, E) be a weighted, directed graph with weight function w : E → {0, 1, …, W } for some nonnegative integer W . Modify Dijkstra’s algorithm to compute the shortest paths from a given source vertex s in O(W V + E) time.

使用一个二维数组实现优先队列。

练习24.3-9 Modify your algorithm from Exercise 24.3-6 to run in O((V + E) lg W ) time. (Hint: How many distinct shortest-path estimates can there be in V - S at any point in time?)

用二叉堆来实现优先队列。

练习24.3-10 Suppose that we are given a weighted, directed graph G = (V, E) in which edges that leave the source vertex s may have negative weights, all other edge weights are nonnegative, and there are no negative-weight cycles. Argue that Dijkstra’s algorithm correctly finds shortest paths from s in this graph.

这种情况下不会破坏已经更新的点的距离。

差分约束和最短路径

线性规划是在满足一组线性不等式的条件下优化一个线性函数。本届讨论线性规划中的一个特例。
在一个差分约束系统中，线性规划矩阵A的每一行包括一个1和一个-1，其他所有项都是0.
引理24.8 设想来那个x是差分约束系统Ax <= b的一个解，设d为任意常数，则x+d也是该差分约束系统的一个解。
可以通过在对应的约束图中寻找最短路径权重来找到一个差分约束系统。我们可以用Bellman-Ford算法来求解差分约束系统。
练习24.4-1 Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:

(-5, -3, 0, -1, -6, -8)

练习24.4-2 Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:

没有解,因为x4 -> x2 -> x3 -> x5 -> x1 -> x4形成了一个负权回路.

练习24.4-3 Can any shortest-path weight from the new vertex v0 in a constraint graph be positive? Explain.

不能。

练习24.4-4 ```


* **练习24.4-5** Show how to modify the Bellman-Ford algorithm slightly so that when it is used to solve a system of difference constraints with m inequalities on n unknowns, the running time is O(nm).

不用v0，一开始令所有的点d为0.


* **练习24.4-6** 

* **练习24.4-7** Show how a system of difference constraints can be solved by a Bellman-Ford-like algorithm that runs on a constraint graph without the extra vertex v0.

不用v0，一开始令所有的点d为0. ```