算法（），中文亦称弗洛伊德算法或佛洛依德算法，是解决任意两点间的最短路径的一种算法，可以正確處理有向圖或负权（但不可存在负权回路）的最短路径問題，同时也被用于计算有向图的传递闭包。
算法的时间复杂度為O(|V|^3)，空间复杂度为O(|V|^2)，其中V是点集。
原理
算法的原理是动态规划。
设D_{i,j,k}为从i到j的只以(1..k)集合中的节点为中间節点的最短路径的长度。
#若最短路径经过点k，则D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}；
#若最短路径不经过点k，则D_{i,j,k}=D_{i,j,k-1}。
因此，D_{i,j,k}=\mbox{min}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})。
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。
算法描述
算法的伪代码描述如下：
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++：[http://www.boost.org/libs/graph/doc/ boost::graph]库下
- C#：[http://www.codeplex.com/quickgraph QuickGraph]和[https://www.nuget.org/packages/QuickGraphPCL/3.6.61114.2 QuickGraphPCL]中均有相关实现方法
- Java：[http://commons.apache.org/sandbox/commons-graph/ Apache Commons Graph]库中
- JavaScript：库中
- MATLAB：[http://www.mathworks.com/matlabcentral/fileexchange/10922 Matlab_bgl]包中
- Perl：[https://metacpan.org/module/Graph Graph]组件下
- Python：SciPy库下（[http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html#scipy.sparse.csgraph.floyd_warshall scipy.sparse.csgraph]），库中也有
- R：[https://cran.r-project.org/web/packages/e1071/index.html e1071]和[https://cran.r-project.org/web/packages/Rfast/index.html Rfast]包内
参考来源
参见
- 图论最短路
- Dijkstra算法
- Bellman-Ford算法
评论 (0)