Floyd-Warshall算法

Floyd-Warshall算法（简称Floyd算法）是一种用于求解加权图中所有顶点对之间最短路径的动态规划算法。该算法支持负权边（但不允许存在负权回路），并能处理有向图和无向图。其核心思想是通过逐步优化路径来找到全局最优解，时间复杂度为$O(V^3)$（V为顶点数），适用于稠密图或需要全局解的场合。

算法原理

Floyd-Warshall算法的核心是动态规划。定义一个三维数组$dist[k][i][j]$，表示从顶点$i$到$j$且仅经过前$k$个顶点的最短路径。通过状态转移方程逐步优化：

$dist[k][i][j]=\min (dist[k-1][i][j],dist[k-1][i][k]+dist[k-1][k][j])$

实际实现中可简化为二维数组，通过滚动数组优化空间复杂度至$O(V^2)$。

算法步骤

1. 初始化距离矩阵：对角线为0，直接相连的边为权重，其余为无穷大。 2. 对每个中间顶点$k$，遍历所有顶点对$(i,j)$，更新最短路径。 3. 重复直至所有中间顶点被考虑。

代码实现

以下是Python实现示例：

  
def floyd_warshall(graph):  
    n = len(graph)  
    dist = [[float('inf')] * n for _ in range(n)]  
    for i in range(n):  
        dist[i][i] = 0  
    for u in range(n):  
        for v, w in graph[u].items():  
            dist[u][v] = w  

    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]  
    return dist  

# 示例输入（邻接表表示）  
graph = {  
    0: {1: 3, 2: 6},  
    1: {0: 3, 2: 2},  
    2: {0: 6, 1: 2}  
}  
print(floyd_warshall(graph))

输出结果：

  
[  
    [0, 3, 5],  
    [3, 0, 2],  
    [5, 2, 0]  
]  

解释：输出矩阵中dist[i][j]表示顶点$i$到$j$的最短距离。

示例分析

图表示例

graph LR A((0)) --3--- B((1)) A --6--- C((2)) B --2--- C

通过算法迭代后，发现顶点0到2的最短路径为0→1→2（总权重5），而非直接路径6。

应用场景

1. 网络路由：计算网络中所有节点间的最短传输路径。 2. 交通规划：优化城市之间的最短行驶路线。 3. 游戏开发：NPC寻路或地图可达性分析。

复杂度与限制

• 时间复杂度：$O(V^3)$，适合小规模图（V≤几百）。
• 空间复杂度：$O(V^2)$。
• 限制：无法处理含负权回路的图（可通过检查对角线元素是否为负来检测）。

扩展：路径重建

若需记录路径，可维护一个前驱矩阵，在状态更新时同步记录中间顶点。

总结

Floyd-Warshall算法是全局最短路径问题的经典解决方案，尤其适合稠密图。尽管复杂度较高，但其实现简洁且功能强大，是图论算法中的重要工具。