Floyd-Warshall算法弗洛伊德算法算法概述Floyd-Warshall算法是由Robert Floyd和Stephen Warshall于1962年提出的一种用于计算图中所有顶点对之间最短路径的经典动态规划算法。该算法能够处理带权有向图或无向图可以包含负权边但不能包含负权环。算法原理Floyd-Warshall算法基于动态规划思想其核心是通过逐步考虑中间节点来优化路径估计动态规划状态dp[k][i][j]dp[k][i][j]dp[k][i][j]表示只使用前kkk个节点作为中间节点时从iii到jjj的最短距离状态转移考虑第kkk个节点是否作为路径的中间节点逐步优化通过增加中间节点来不断优化路径长度算法步骤初始化创建距离矩阵distdistdist其中dist[i][j]dist[i][j]dist[i][j]表示从iii到jjj的直接距离如果iji jij则dist[i][j]0dist[i][j] 0dist[i][j]0如果iii和jjj之间有边则dist[i][j]w(i,j)dist[i][j] w(i, j)dist[i][j]w(i,j)否则dist[i][j]∞dist[i][j] \inftydist[i][j]∞动态规划迭代对于每个中间节点kkk从 1 到VVV对于每对顶点(i,j)(i, j)(i,j)更新dist[i][j]min⁡(dist[i][j],dist[i][k]dist[k][j])dist[i][j] \min(dist[i][j], dist[i][k] dist[k][j])dist[i][j]min(dist[i][j],dist[i][k]dist[k][j])结果输出最终的distdistdist矩阵包含所有顶点对之间的最短距离数学表达设G(V,E)G (V, E)G(V,E)为一个带权图其中VVV是顶点集合∣V∣n|V| n∣V∣nEEE是边集合w(i,j)w(i, j)w(i,j)表示边(i,j)(i, j)(i,j)的权重Floyd-Warshall算法维护的距离矩阵DDD满足D(k)[i][j]min⁡{D(k−1)[i][j]D(k−1)[i][k]D(k−1)[k][j]D^{(k)}[i][j] \min \begin{cases} D^{(k-1)}[i][j] \\ D^{(k-1)}[i][k] D^{(k-1)}[k][j] \end{cases}D(k)[i][j]min{D(k−1)[i][j]D(k−1)[i][k]D(k−1)[k][j]​其中D(k)[i][j]D^{(k)}[i][j]D(k)[i][j]表示只使用前kkk个节点作为中间节点时从iii到jjj的最短距离。时间复杂度时间复杂度O(V3)O(V^3)O(V3)空间复杂度O(V2)O(V^2)O(V2)其中VVV是顶点数算法特点优点能够计算所有顶点对之间的最短路径算法实现简单易于理解可以处理含负权边的图但不能含负权环能够检测负权环缺点时间复杂度较高不适用于大规模图空间复杂度较高需要O(V2)O(V^2)O(V2)的存储空间对于稀疏图效率较低应用场景全最短路径计算需要计算图中所有顶点对之间的最短路径网络分析分析网络中任意两点间的最短距离交通规划城市间交通网络的最短路径分析图像处理某些图像处理算法中的距离计算伪代码function FloydWarshall(Graph): n ← number of vertices in Graph dist ← new n×n matrix // 初始化距离矩阵 for i from 1 to n: for j from 1 to n: if i j: dist[i][j] ← 0 else if (i, j) ∈ Graph: dist[i][j] ← weight(i, j) else: dist[i][j] ← ∞ // 动态规划迭代 for k from 1 to n: for i from 1 to n: for j from 1 to n: if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] ← dist[i][k] dist[k][j] // 检测负权环 for i from 1 to n: if dist[i][i] 0: error Graph contains a negative-weight cycle return dist实现示例Python实现deffloyd_warshall(graph):# 获取所有节点nodeslist(graph.keys())nlen(nodes)node_index{node:ifori,nodeinenumerate(nodes)}# 初始化距离矩阵dist[[float(infinity)]*nfor_inrange(n)]# 设置对角线为0foriinrange(n):dist[i][i]0# 填充初始距离foruingraph:forv,weightingraph[u].items():inode_index[u]jnode_index[v]dist[i][j]weight# 动态规划迭代forkinrange(n):foriinrange(n):forjinrange(n):ifdist[i][k]dist[k][j]dist[i][j]:dist[i][j]dist[i][k]dist[k][j]# 检测负权环foriinrange(n):ifdist[i][i]0:raiseValueError(图中存在负权环)# 转换为节点名称的字典result{}fori,uinenumerate(nodes):result[u]{}forj,vinenumerate(nodes):result[u][v]dist[i][j]returnresult算法分析空间优化Floyd-Warshall算法可以使用空间优化技术将空间复杂度从O(V2)O(V^2)O(V2)降低到O(V)O(V)O(V)deffloyd_warshall_space_optimized(graph):nodeslist(graph.keys())nlen(nodes)node_index{node:ifori,nodeinenumerate(nodes)}# 使用一维数组进行空间优化dist[float(infinity)]*nforuingraph:forv,weightingraph[u].items():inode_index[u]jnode_index[v]dist[i*nj]weight# 动态规划迭代forkinrange(n):foriinrange(n):forjinrange(n):ifdist[i*nk]dist[k*nj]dist[i*nj]:dist[i*nj]dist[i*nk]dist[k*nj]returndist路径重构除了计算最短距离Floyd-Warshall算法还可以重构最短路径deffloyd_warshall_with_path(graph):nodeslist(graph.keys())nlen(nodes)node_index{node:ifori,nodeinenumerate(nodes)}# 初始化距离矩阵和前驱矩阵dist[[float(infinity)]*nfor_inrange(n)]next_node[[-1]*nfor_inrange(n)]foriinrange(n):dist[i][i]0foruingraph:forv,weightingraph[u].items():inode_index[u]jnode_index[v]dist[i][j]weight next_node[i][j]j# 动态规划迭代forkinrange(n):foriinrange(n):forjinrange(n):ifdist[i][k]dist[k][j]dist[i][j]:dist[i][j]dist[i][k]dist[k][j]next_node[i][j]next_node[i][k]# 获取路径的函数defget_path(i,j):ifnext_node[i][j]-1:return[]path[i]whilei!j:inext_node[i][j]path.append(i)returnpathreturndist,get_path算法比较与Johnson算法的比较特性Floyd-WarshallJohnson时间复杂度O(V3)O(V^3)O(V3)O(V2log⁡VV⋅E)O(V^2 \log V V \cdot E)O(V2logVV⋅E)空间复杂度O(V2)O(V^2)O(V2)O(V2)O(V^2)O(V2)适用场景密集图稀疏图实现复杂度简单较复杂与多次Dijkstra的比较特性Floyd-Warshall多次Dijkstra时间复杂度O(V3)O(V^3)O(V3)O(V⋅(VE)log⁡V)O(V \cdot (V E) \log V)O(V⋅(VE)logV)空间复杂度O(V2)O(V^2)O(V2)O(VE)O(V E)O(VE)适用场景密集图稀疏图实现复杂度简单较复杂注意事项确保图中不包含负权环否则算法会检测到并报错对于大规模图考虑使用Johnson算法或其他优化方法在实现时注意处理无穷大的表示和比较可以通过空间优化减少内存使用总结Floyd-Warshall算法作为计算所有顶点对最短路径的经典算法具有重要的理论价值和实际应用意义。虽然其时间复杂度较高但在需要计算全最短路径的场景中具有不可替代的作用。算法的动态规划思想和实现简单性使其成为图论教学和实际应用中的重要工具。