编辑“︁Floyd-Warshall算法”︁

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

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

<math>  
dist[k][i][j] = \min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])  
</math>  

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

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

== 代码实现 ==  
以下是Python实现示例：  

<syntaxhighlight lang="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))  
</syntaxhighlight>  

'''输出结果'''：  
<pre>  
[  
    [0, 3, 5],  
    [3, 0, 2],  
    [5, 2, 0]  
]  
</pre>  
解释：输出矩阵中<code>dist[i][j]</code>表示顶点<math>i</math>到<math>j</math>的最短距离。

== 示例分析 ==  
=== 图表示例 ===  
<mermaid>  
graph LR  
    A((0)) --3--- B((1))  
    A --6--- C((2))  
    B --2--- C  
</mermaid>  

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

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

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

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

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]