Floyd-Warshall算法

Template:TA Template:Infobox Algorithm Template:图搜索算法 Template:Lang算法（Template:Lang-en），中文亦称弗洛伊德算法或佛洛依德算法，是解决任意两点间的最短路径的一种算法，可以正確處理有向圖或负权（但不可存在负权回路）的最短路径問題，同时也被用于计算有向图的传递闭包。

Template:Lang算法的时间复杂度為$O(|V{|}^3)$，空间复杂度为$O(|V{|}^2)$，其中$V$是点集。

原理

Template:Lang算法的原理是动态规划。

设$D_{i,j,k}$为从$i$到$j$的只以$(1..k)$集合中的节点为中间節点的最短路径的长度。

1. 若最短路径经过点k，则$D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}$；
2. 若最短路径不经过点k，则$D_{i,j,k}=D_{i,j,k-1}$。

因此，$D_{i,j,k}=\text{min}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})$。

在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

算法描述

Template:Lang算法的伪代码描述如下：

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

其中dist[i][j]表示由點$i$到點$j$的代價，當其為 ∞ 表示兩點之間沒有任何連接。

使用动态规划的算法

• 最长公共子序列
• 维特比算法

实现

Floyd算法在不同的编程语言中均有大量的实现方法：

• C++：boost::graphTemplate:Wayback库下
• C#：QuickGraphTemplate:Wayback和QuickGraphPCLTemplate:Wayback中均有相关实现方法
• Java：Apache Commons GraphTemplate:Wayback库中
• JavaScript：Template:Tsl库中
• MATLAB：Matlab_bglTemplate:Wayback包中
• Perl：GraphTemplate:Wayback组件下
• Python：SciPy库下（scipy.sparse.csgraphTemplate:Wayback），Template:Tsl库中也有
• R：e1071Template:Wayback和RfastTemplate:Wayback包内

参见

• 图论最短路
• Dijkstra算法
• Bellman-Ford算法