多源最短路

请确保自己已经了解图的相关内容。包括但不限于：

  • 图，邻接表，邻接矩阵
  • 路径，最短路，权，环
  • 有向图，无向图
  • Dijkstra算法，Bellman-Ford算法

文中所有的证明都是不严谨的，详细数学证明可移步《算法导论》相关章节。

定义

顾名思义，求一张图上所有节点到其他可连通节点的最短路径。

最短路算法 Floyd Johnson Dijkstra Bellman–Ford
最短路类型 每对结点之间的最短路 每对结点之间的最短路 单源最短路 单源最短路
作用于 任意图 任意图 非负权图 任意图
能否检测负环？ 能 能 不能 能
时间复杂度 O(N3)O(N^3) O(NMlog⁡M)O(NM\log M) O(Mlog⁡M)O(M\log M) O(NM)O(NM)

注：表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。

Floyd 算法

弗洛伊德算法可以用来求任意两个结点之间的最短路。

复杂度比较高，但是常数小，容易实现（只有三个 for）。

适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）

实现

我们定义一个数组 f[k][x][y]，表示只允许经过结点 1 到 k（也就是说，在子图 V'=1, 2,..., k 中的路径，注意，x与y不一定在这个子图中），结点x到结点y的最短路长度。

很显然，f[n][x][y] 就是结点x到结点y的最短路长度（因为 V'=1, 2,..., k 即为V本身，其表示的最短路径就是所求路径）。

接下来考虑如何求出 f 数组的值。

f[0][x][y]：x与y的边权，或者0，或者 +inf（f[0][x][y]什么时候应该是 +inf？当x与y间有直接相连的边的时候，为它们的边权；当x = y的时候为零，因为到本身的距离为零；当x与y没有直接相连的边的时候，为 +inf）。

f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])（f[k-1][x][y]，为不经过k点的最短路径，而 f[k-1][x][k]+f[k-1][k][y]，为经过了k点的最短路）。

上面两行都显然是对的，所以说这个做法空间是 O(N^3)，我们需要依次增加问题规模（k从1到n），判断任意两点在当前问题规模下的最短路。

1
2
3
4
for k in range(1, n + 1):
        for x in range(1, n + 1):
            for y in range(1, n + 1):
                f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y])

因为第一维对结果无影响，我们可以发现数组的第一维是可以省略的，于是可以直接改成 f[x][y] = min(f[x][y], f[x][k]+f[k][y])。

证明第一维对结果无影响

我们注意到如果放在一个给定第一维k二维数组中，f[x][k] 与 f[k][y] 在某一行和某一列。而 f[x][y] 则是该行和该列的交叉点上的元素。

现在我们需要证明将 f[k][x][y] 直接在原地更改也不会更改它的结果：我们注意到 f[k][x][y] 的涵义是第一维为 k-1 这一行和这一列的所有元素的最小值，包含了 f[k-1][x][y]，那么在原地进行更改也不会改变最小值的值，因为如果将该三维矩阵压缩为二维，则所求结果 f[x][y] 一开始即为原 f[k-1][x][y] 的值，最后依然会成为该行和该列的最小值。故可以压缩。

1
2
3
4
for k in range(1, n + 1):
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            f[x][y] = min(f[x][y], f[x][k] + f[k][y])

综上，时间复杂度是 O(N^3)，空间复杂度是 O(N^2)。

前驱矩阵

当然，很多时候我们需要的不仅仅是最短路径的距离，还要得到最短路径上经过的节点。此时我们可以引入一个前驱矩阵来实现这一功能。

前驱矩阵在弗洛伊德算法中用于记录每个节点对之间最短路径的前驱节点。通过其记录的数据，我们可以追溯从起始节点到目标节点的路径。通过不断查询前驱矩阵，可以从目标节点反向追溯到起始节点，从而得到完整的路径。同时，使用前驱矩阵可以在最短路径计算完成后快速查询任意两个节点之间的最短路径，而不需要重新计算。

使用前驱矩阵重构路径的步骤

  1. 初始化：初始化前驱矩阵pred，如果有直接边连接节点i和节点j，则pred[i][j]设为i。
  2. 更新前驱矩阵：在更新距离矩阵dist的同时更新前驱矩阵pred。如果通过中间节点k可以缩短从节点i到节点j的路径，则更新pred[i][j]为pred[k][j]。
  3. 重构路径：从目标节点开始，逐步查找前驱节点，直到到达起始节点，记录所经过的节点即可得到路径。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def floyd_warshall_with_predecessor(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    pred = [[None] * n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] != float('inf'):
                dist[i][j] = graph[i][j]
                pred[i][j] = i

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    pred[i][j] = pred[k][j]

    return dist, pred

def reconstruct_path(predecessors, start, end):
    if predecessors[start][end] is None:
        return []  # 表示没有路径
    path = [end]
    while end != start:
        end = predecessors[start][end]
        path.append(end)
    path.reverse()
    return path

# 示例图
graph = [
    [0, 3, float('inf'), 5],
    [2, 0, float('inf'), 4],
    [float('inf'), 1, 0, float('inf')],
    [float('inf'), float('inf'), 2, 0]
]

distances, predecessors = floyd_warshall_with_predecessor(graph)

print("All-pairs shortest path matrix:")
for row in distances:
    print(row)

print("\nPredecessor matrix:")
for row in predecessors:
    print(row)

start, end = 0, 3
path = reconstruct_path(predecessors, start, end)
print(f"\nShortest path from {start} to {end}: {path}")

运行结果
1
2
3
4
5
6
7
8
9
10
11
12
13
All-pairs shortest path matrix:
[0, 3, 7, 5]
[2, 0, 6, 4]
[3, 1, 0, 5]
[5, 4, 2, 0]

Predecessor matrix:
[None, 0, 1, 0]
[1, None, 1, 1]
[1, 2, None, 1]
[2, 2, 3, None]

Shortest path from 0 to 3: [0, 1, 3]

Johnson 算法

Johnson 和 Floyd 一样，是一种能求出无负环图上任意两点间最短路径的算法。该算法在 1977 年由 Donald B. Johnson 提出。

任意两点间的最短路可以通过枚举起点，跑 n 次 Bellman–Ford 算法解决，时间复杂度是 O(m*n^2) 的，也可以直接用 Floyd 算法解决，时间复杂度为 O(n^3)。

注意到堆优化的 Dijkstra 算法求单源最短路径的时间复杂度比 Bellman–Ford 更优，如果枚举起点，跑 n 次 Dijkstra 算法，就可以在 O(nmlogm)（取决于 Dijkstra 算法的实现）的时间复杂度内解决本问题，比上述跑 n 次 Bellman–Ford 算法的时间复杂度更优秀，在稀疏图上也比 Floyd 算法的时间复杂度更加优秀。

但 Dijkstra 算法不能正确求解带负权边的最短路，因此我们需要对原图上的边进行预处理，确保所有边的边权均非负。

我们新建一个虚拟节点（在这里我们就设它的编号为 0）。从这个点向其他所有点连一条边权为 0 的边。

接下来用 Bellman–Ford 算法求出从 0 号点到其他所有点的最短路，记为 h_i。

假如存在一条从 u 点到 v 点，边权为 w 的边，则我们将该边的边权重新设置为 w+h_u-h_v。

接下来以每个点为起点，跑 n 轮 Dijkstra 算法即可求出任意两点间的最短路了。

一开始的 Bellman–Ford 算法并不是时间上的瓶颈，若使用 priority_queue 实现 Dijkstra 算法，该算法的时间复杂度是 O(nmlogm)。

正确性证明

在重新标记后的图上，从 s 点到 t 点的一条路径 s -> p_1 -> p_2 -> ... -> p_k -> t 的长度表达式如下：

(w(s,p1)+hs−hp1)+(w(p1,p2)+hp1−hp2)+⋯+(w(pk,t)+hpk−ht)(w(s,p_1)+h_s-h_{p_1})+(w(p_1,p_2)+h_{p_1}-h_{p_2})+ \dots +(w(p_k,t)+h_{p_k}-h_t)

化简后得到：

w(s,p1)+w(p1,p2)+⋯+w(pk,t)+hs−htw(s,p_1)+w(p_1,p_2)+ \dots +w(p_k,t)+h_s-h_t

无论我们从 s 到 t 走的是哪一条路径，h_s - h_t的值是不变的，这正与物理中势能的性质相吻合！

为了方便，下面我们就把 h_i 称为 i 点的势能。

上面的新图中 s -> t 的最短路的长度表达式由两部分组成，前面的边权和为原图中 s -> t 的最短路，后面则是两点间的势能差。因为两点间势能的差为定值，因此原图上 s -> t 的最短路与新图上 s -> t 的最短路相对应。

到这里我们的正确性证明已经解决了一半——我们证明了重新标注边权后图上的最短路径仍然是原来的最短路径。接下来我们需要证明新图中所有边的边权非负，因为在非负权图上，Dijkstra 算法能够保证得出正确的结果。

根据三角形不等式，图上任意一边 (u,v) 上两点满足：hv≤hu+w(u,v)h_v \leq h_u + w(u,v)。这条边重新标记后的边权为 w′(u,v)=w(u,v)+hu−hv≥0w'(u,v)=w(u,v)+h_u-h_v \geq 0。这样我们证明了新图上的边权均非负。

这样，我们就证明了 Johnson 算法的正确性。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import heapq

def bellman_ford(graph, source):
    distance = {v: float('inf') for v in graph}
    distance[source] = 0

    for _ in range(len(graph) - 1):
        for u in graph:
            for v, weight in graph[u]:
                if distance[u] + weight < distance[v]:
                    distance[v] = distance[u] + weight

    # 检查负权重环路
    for u in graph:
        for v, weight in graph[u]:
            if distance[u] + weight < distance[v]:
                raise ValueError("Graph contains a negative-weight cycle")

    return distance

def dijkstra(graph, source):
    pq = [(0, source)]
    distance = {v: float('inf') for v in graph}
    distance[source] = 0

    while pq:
        current_distance, u = heapq.heappop(pq)
        
        if current_distance > distance[u]:
            continue

        for v, weight in graph[u]:
            distance_v = current_distance + weight
            if distance_v < distance[v]:
                distance[v] = distance_v
                heapq.heappush(pq, (distance_v, v))

    return distance

def johnson(graph):
    new_graph = {v: list(graph[v]) for v in graph}
    new_graph['new_node'] = [(v, 0) for v in graph]

    # 运行Bellman-Ford算法
    h = bellman_ford(new_graph, 'new_node')
    del new_graph['new_node']

    # 调整边权重
    for u in graph:
        for i, (v, weight) in enumerate(new_graph[u]):
            new_graph[u][i] = (v, weight + h[u] - h[v])

    distances = {}
    for u in graph:
        distances[u] = dijkstra(new_graph, u)
        for v in graph:
            distances[u][v] = distances[u][v] - h[u] + h[v]

    return distances

# 示例图，使用邻接表表示
graph = {
    'A': [('B', -2)],
    'B': [('C', 1)],
    'C': [('A', 4)]
}

# 计算所有节点之间的最短路径
distances = johnson(graph)

# 打印结果
print("All-pairs shortest path matrix:")
for u in distances:
    for v in distances[u]:
        print(f"Shortest path from {u} to {v} is {distances[u][v]}")

运行结果
1
2
3
4
5
6
7
8
9
10
All-pairs shortest path matrix:
Shortest path from A to A is 0
Shortest path from A to B is -2
Shortest path from A to C is -1
Shortest path from B to A is 5
Shortest path from B to B is 0
Shortest path from B to C is 1
Shortest path from C to A is 4
Shortest path from C to B is 2
Shortest path from C to C is 0