Floyd-Warshall算法（英语：Floyd-Warshall algorithm），中文亦称弗洛伊德算法或佛洛依德算法[1]，是解决任意两点间的最短路径的一种算法[2]，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包[3]。

Floyd-Warshall算法的时间复杂度为 � ( | � | 3 ) O(|V|^{3})[4]，空间复杂度为 � ( | � | 2 ) O(|V|^{2})，其中 � V是点集。

目录 1 原理 2 算法描述 3 使用动态规划的算法 4 实现 5 参考来源 6 参见 原理 Floyd-Warshall算法的原理是动态规划[5]。

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

若最短路径经过点k，则 � � , � , �

� � , � , � − 1 + � � , � , � − 1 D_{{i,j,k}}=D_{{i,k,k-1}}+D_{{k,j,k-1}}； 若最短路径不经过点k，则 � � , � , �

� � , � , � − 1 D_{{i,j,k}}=D_{{i,j,k-1}}。 因此， � � , � , �

min ( � � , � , � − 1 , � � , � , � − 1 + � � , � , � − 1 ) D_{{i,j,k}}={\mbox{min}}(D_{{i,j,k-1}},D_{{i,k,k-1}}+D_{{k,j,k-1}})。

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

算法描述 Floyd-Warshall算法的伪代码描述如下：

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的代价，当其为 ∞ 表示两点之间没有任何连接。

使用动态规划的算法 最长公共子序列 Viterbi算法 实现 Floyd算法在不同的编程语言中均有大量的实现方法：

C++：boost::graph（页面存档备份，存于互联网档案馆）库下 C#：QuickGraph（页面存档备份，存于互联网档案馆）和QuickGraphPCL（页面存档备份，存于互联网档案馆）中均有相关实现方法 Java：Apache Commons Graph（页面存档备份，存于互联网档案馆）库中 JavaScript：Cytoscape库中 MATLAB：Matlab_bgl（页面存档备份，存于互联网档案馆）包中 Perl：Graph（页面存档备份，存于互联网档案馆）组件下 Python：SciPy库下（scipy.sparse.csgraph（页面存档备份，存于互联网档案馆）），NetworkX库中也有 R：e1071（页面存档备份，存于互联网档案馆）和Rfast（页面存档备份，存于互联网档案馆）包内

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: