浅谈 Johnson 算法

1318 字

7 分钟

浅谈 Johnson 算法

2024-11-17

算法

/

Johnson算法

/

图论

1. 算法思想#

Johnson 算法用于解决带权有向图中所有节点对之间的最短路径问题，它结合了 Bellman-Ford 算法和 Dijkstra 算法的优点。首先，通过添加一个虚拟节点 s 到图中，将所有边的权重进行重新赋值（重赋权技巧），使得图中不存在负权环的同时，利用 Bellman-Ford 算法计算出从虚拟节点 s 到图中每个节点的最短距离 h(v)。然后，对于图中的每一对节点 u 和 v，将原边权重 w(u, v) 替换为新的权重 w'(u, v) = w(u, v) + h(u) - h(v)，这样处理后可以保证新的权重是非负的（通过利用最短距离的性质）。最后，针对每一个节点作为源点，使用 Dijkstra 算法来计算经过重赋权后的图中到其他节点的最短路径，再根据重赋权的关系将计算出的距离转换回原图中的最短路径距离。

2. 代码示例#

（Python 代码，以下是简化实现，假设输入的图用邻接矩阵表示，图中不存在负权环，节点编号从 0 开始）

1
    import math
2

3
    def bellman_ford(graph, num_vertices):
4
        """
5
        Bellman-Ford 算法，用于计算从虚拟源点到各节点的最短距离
6
        """
7
        # 初始化距离数组，初始设为无穷大
8
        dist = [math.inf] * num_vertices
9
        dist[0] = 0
10
        for _ in range(num_vertices - 1):
11
            for u in range(num_vertices):
12
                for v in range(num_vertices):
13
                    if graph[u][v]!= math.inf:
14
                        if dist[u] + graph[u][v] < dist[v]:
15
                            dist[v] = dist[u] + graph[u][v]
16
        return dist
17

18
    def dijkstra(graph, source, num_vertices):
19
        """
20
        Dijkstra 算法，用于计算从给定源点到其他节点的最短路径
21
        """
22
        # 初始化距离数组，初始设为无穷大
23
        dist = [math.inf] * num_vertices
24
        dist[source] = 0
25
        visited = [false] * num_vertices
26
        for _ in range(num_vertices):
27
            min_dist = math.inf
28
            min_index = -1
29
            for v in range(num_vertices):
30
                if not visited[v] and dist[v] < min_dist:
31
                    min_dist = dist[v]
32
                    min_index = v
33
            visited[min_index] = true
34
            for v in range(num_vertices):
35
                if graph[min_index][v]!= math.inf and dist[min_index] + graph[min_index][v] < dist[v]:
36
                    dist[v] = dist[min_index] + graph[min_index][v]
37
        return dist
38

39
    def johnson(graph):
40
        """
41
        Johnson 算法实现
42
        """
43
        num_vertices = len(graph)
44
        # 添加虚拟源点，构建新的图
45
        new_graph = [[math.inf] * (num_vertices + 1) for _ in range(num_vertices + 1)]
46
        for i in range(num_vertices):
47
            for j in range(num_vertices):
48
                new_graph[i][j] = graph[i][j]
49
        # 运行 Bellman-Ford 算法
50
        h = bellman_ford(new_graph, num_vertices + 1)[0:num_vertices]
51
        # 重赋权边
52
        new_weight_graph = [[math.inf] * num_vertices for _ in range(num_vertices)]
53
        for u in range(num_vertices):
54
        for v in range(num_vertices):
55
            if graph[u][v]!= math.inf:
56
                new_weight_graph[u][v] = graph[u][v] + h[u] - h[v]
57
        # 对每个节点作为源点运行 Dijkstra 算法，存储所有节点对最短路径结果
58
        all_pairs_shortest_paths = []
59
        for source in range(num_vertices):
60
            dist = dijkstra(new_weight_graph, source, num_vertices)
61
            # 还原原权重下的最短路径距离
62
            for v in range(num_vertices):
63
                if dist[v]!= math.inf:
64
                    dist[v] = dist[v] - h[source] + h[v]
65
            all_pairs_shortest_paths.append(dist)
66
        return all_pairs_shortest_paths

你可以使用以下方式调用这个函数：

1
    # 示例图，用邻接矩阵表示，无穷大表示无边相连
2
    graph = [
3
        [0, 3, math.inf, 7],
4
        [8, 0, 2, math.inf],
5
        [5, math.inf, 0, 1],
6
        [2, math.inf, math.inf, 0]
7
    ]
8
    shortest_paths = johnson(graph)
9
    print(shortest_paths)

3. 复杂度分析#

时间复杂度：
- 第一步 Bellman-Ford 算法的时间复杂度为 $O(V^3)$ ，其中 V 是图中节点的数量，因为它要对每条边进行 V - 1 次松弛操作，每次松弛操作遍历所有边（在邻接矩阵表示下），时间复杂度为 $O(V^2)$ ，整体就是 $O(V^3)$ 。
- 第二步对每个节点运行 Dijkstra 算法，若使用二叉堆实现优先队列的 Dijkstra 算法，每次时间复杂度为 $O((V + E) \log V)$ ，E 是边数，总共运行 V 次，这部分时间复杂度就是 $O(V (V + E) \log V)$ 。在稀疏图（E 接近 V）情况下，时间复杂度约为 $O(V^2 \log V)$ ，在稠密图（E 接近 $V^2$ ）情况下，时间复杂度约为 $O(V^3 \log V)$ 。所以 Johnson 算法总的时间复杂度在最坏情况下为 $O(V^3 \log V)$ 。
空间复杂度：需要存储图的相关信息（如邻接矩阵等）、距离数组等，在 Bellman-Ford 和 Dijkstra 算法执行过程中还需要一些临时空间，总体空间复杂度主要取决于图的表示方式以及节点数量，一般来说在 $O(V^2)$ 级别（使用邻接矩阵表示图时），V 为节点数量。

4. 正确性证明#

重赋权后不存在负权边：根据 Bellman-Ford 算法计算出的 h(v) 是从虚拟节点 s 到节点 v 的最短距离。对于图中任意边 (u, v)，有 w'(u, v) = w(u, v) + h(u) - h(v)，根据最短路径的三角不等式（从 s 到 v 的最短路径长度不会大于从 s 经过 u 再到 v 的路径长度），可得 h(v) ≤ h(u) + w(u, v)，移项后就是 w'(u, v) = w(u, v) + h(u) - h(v) ≥ 0，所以重赋权后的边权重都是非负的。
计算的最短路径等价于原图最短路径：设 d(u, v) 是原图中从 u 到 v 的最短路径距离，d'(u, v) 是重赋权后图中从 u 到 v 的最短路径距离。根据重赋权的定义以及最短路径的性质，对于任意节点对 u 和 v，有 d'(u, v) = d(u, v) + h(u) - h(v)，在计算出重赋权后图中的最短路径 d'(u, v) 后，通过还原操作 d(u, v) = d'(u, v) - h(u) + h(v) 就可以得到原图中的最短路径距离，所以 Johnson 算法最终计算出的所有节点对之间的最短路径是正确的。