6.9 多源最短路径

ITCharge大约 6 分钟

6.9 多源最短路径

1. 多源最短路径简介

多源最短路径（All-Pairs Shortest Paths）：对于一个带权图 $G = (V, E)$ ，计算图中任意两个顶点之间的最短路径长度。

多源最短路径问题的核心是找到图中任意两个顶点之间的最短路径。这个问题在许多实际应用中都非常重要，比如：

网络路由中的路由表计算
地图导航系统中的距离矩阵计算
社交网络中的最短关系链分析
交通网络中的最优路径规划

常见的解决多源最短路径问题的算法包括：

Floyd-Warshall 算法：一种动态规划算法，可以处理负权边，但不能处理负权环。
Johnson 算法：结合了 Bellman-Ford 算法和 Dijkstra 算法，可以处理负权边，但不能处理负权环。
重复 Dijkstra 算法：对每个顶点运行一次 Dijkstra 算法，适用于无负权边的图。

2. Floyd-Warshall 算法

2.1 Floyd-Warshall 算法的算法思想

Floyd-Warshall 算法：一种动态规划算法，通过逐步考虑中间顶点来更新任意两点之间的最短路径。

Floyd-Warshall 算法的核心思想是：

对于图中的任意两个顶点 $i$ 和 $j$ ，考虑是否存在一个顶点 $k$ ，使得从 $i$ 到 $k$ 再到 $j$ 的路径比已知的从 $i$ 到 $j$ 的路径更短
如果存在这样的顶点 $k$ ，则更新从 $i$ 到 $j$ 的最短路径
通过考虑所有可能的中间顶点 $k$ ，最终得到任意两点之间的最短路径

2.2 Floyd-Warshall 算法的实现步骤

初始化距离矩阵 $dist$ ，其中 $dist[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 的最短路径长度
对于每对顶点 $(i, j)$ ，如果存在边 $(i, j)$ ，则 $dist[i][j]$ 设为边的权重，否则设为无穷大
对于每个顶点 $k$ $k$ ，作为中间顶点：
- 对于每对顶点 $(i, j)$ ，如果 $dist[i][k] + dist[k][j] < dist[i][j]$ ，则更新 $dist[i][j]$
重复步骤 3，直到考虑完所有可能的中间顶点
返回最终的距离矩阵

2.3 Floyd-Warshall 算法的实现代码

def floyd_warshall(graph, n):
    # 初始化距离矩阵
    dist = [[float('inf') for _ in range(n)] for _ in range(n)]
    
    # 设置直接相连的顶点之间的距离
    for i in range(n):
        dist[i][i] = 0
        for j, weight in graph[i].items():
            dist[i][j] = weight
    
    # 考虑每个顶点作为中间顶点
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

代码解释：

graph 是一个字典，表示图的邻接表。例如，graph[0] = {1: 3, 2: 4} 表示从节点 0 到节点 1 的边权重为 3，到节点 2 的边权重为 4。
n 是图中顶点的数量。
dist 是一个二维数组，存储任意两点之间的最短路径长度。
首先初始化距离矩阵，将对角线元素设为 0，表示顶点到自身的距离为 0。
然后设置直接相连的顶点之间的距离。
主循环中，对于每个顶点 $k$ ，考虑它作为中间顶点时，是否能缩短其他顶点之间的距离。
最终返回的距离矩阵中， $dist[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 的最短路径长度。

2.4 Floyd-Warshall 算法复杂度分析

时间复杂度： $O(V^3)$
- 需要三层嵌套循环，分别遍历所有顶点
- 因此总时间复杂度为 $O(V^3)$
空间复杂度： $O(V^2)$
- 需要存储距离矩阵，大小为 $O(V^2)$
- 不需要额外的空间来存储图的结构，因为使用邻接表表示

Floyd-Warshall 算法的主要优势在于：

实现简单，容易理解
可以处理负权边
可以检测负权环（如果某个顶点到自身的距离变为负数，说明存在负权环）
适用于稠密图

主要缺点：

时间复杂度较高，不适用于大规模图
空间复杂度较高，需要存储完整的距离矩阵
不能处理负权环

3. Johnson 算法

3.1 Johnson 算法的算法思想

Johnson 算法：一种结合了 Bellman-Ford 算法和 Dijkstra 算法的多源最短路径算法，可以处理负权边，但不能处理负权环。

Johnson 算法的核心思想是：

通过重新赋权，将图中的负权边转换为非负权边
对每个顶点运行一次 Dijkstra 算法，计算最短路径
将结果转换回原始权重

3.2 Johnson 算法的实现步骤

添加一个新的顶点 $s$ ，并添加从 $s$ 到所有其他顶点的边，权重为 0
使用 Bellman-Ford 算法计算从 $s$ 到所有顶点的最短路径 $h(v)$
重新赋权：对于每条边 $(u, v)$ ，新的权重为 $w(u, v) + h(u) - h(v)$
对每个顶点 $v$ ，使用 Dijkstra 算法计算从 $v$ 到所有其他顶点的最短路径
将结果转换回原始权重：对于从 $u$ 到 $v$ 的最短路径，原始权重为 $d(u, v) - h(u) + h(v)$

3.3 Johnson 算法的实现代码

from collections import defaultdict
import heapq

def johnson(graph, n):
    # 添加新顶点 s
    new_graph = defaultdict(dict)
    for u in graph:
        for v, w in graph[u].items():
            new_graph[u][v] = w
        new_graph[n][u] = 0  # 从 s 到所有顶点的边权重为 0
    
    # 使用 Bellman-Ford 算法计算 h(v)
    h = [float('inf')] * (n + 1)
    h[n] = 0
    
    for _ in range(n):
        for u in new_graph:
            for v, w in new_graph[u].items():
                if h[v] > h[u] + w:
                    h[v] = h[u] + w
    
    # 检查是否存在负权环
    for u in new_graph:
        for v, w in new_graph[u].items():
            if h[v] > h[u] + w:
                return None  # 存在负权环
    
    # 重新赋权
    reweighted_graph = defaultdict(dict)
    for u in graph:
        for v, w in graph[u].items():
            reweighted_graph[u][v] = w + h[u] - h[v]
    
    # 对每个顶点运行 Dijkstra 算法
    dist = [[float('inf') for _ in range(n)] for _ in range(n)]
    for source in range(n):
        # 初始化距离数组
        d = [float('inf')] * n
        d[source] = 0
        
        # 使用优先队列
        pq = [(0, source)]
        visited = set()
        
        while pq:
            current_dist, u = heapq.heappop(pq)
            if u in visited:
                continue
            visited.add(u)
            
            for v, w in reweighted_graph[u].items():
                if d[v] > current_dist + w:
                    d[v] = current_dist + w
                    heapq.heappush(pq, (d[v], v))
        
        # 转换回原始权重
        for v in range(n):
            if d[v] != float('inf'):
                dist[source][v] = d[v] - h[source] + h[v]
    
    return dist

代码解释：

graph 是一个字典，表示图的邻接表。
n 是图中顶点的数量。
首先添加一个新的顶点 $s$ ，并添加从 $s$ 到所有其他顶点的边，权重为 0。
使用 Bellman-Ford 算法计算从 $s$ 到所有顶点的最短路径 $h(v)$ 。
检查是否存在负权环，如果存在则返回 None。
重新赋权，将图中的负权边转换为非负权边。
对每个顶点运行一次 Dijkstra 算法，计算最短路径。
将结果转换回原始权重，得到最终的距离矩阵。

3.4 Johnson 算法复杂度分析

时间复杂度： $O(VE \log V)$
- 需要运行一次 Bellman-Ford 算法，时间复杂度为 $O(VE)$
- 需要运行 $V$ 次 Dijkstra 算法，每次时间复杂度为 $O(E \log V)$
- 因此总时间复杂度为 $O(VE \log V)$
空间复杂度： $O(V^2)$
- 需要存储距离矩阵，大小为 $O(V^2)$
- 需要存储重新赋权后的图，大小为 $O(E)$
- 因此总空间复杂度为 $O(V^2)$