Floyd-Warshall算法

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

算法的时间复杂度為，空间复杂度为，其中是点集。

原理
算法的原理是动态规划。

设为从到的只以集合中的节点为中间節点的最短路径的长度。
若最短路径经过点k，则；
若最短路径不经过点k，则。

因此，。

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

算法描述

算法的伪代码描述如下：
 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]表示由點到點的代價，當其為 ∞ 表示兩點之間沒有任何連接。

使用动态规划的算法 
 最长公共子序列
 Viterbi算法

实现
Floyd算法在不同的编程语言中均有大量的实现方法：
 C++：boost::graph库下
 C#：QuickGraph和QuickGraphPCL中均有相关实现方法
 Java：Apache Commons Graph库中
 JavaScript：库中
 MATLAB：Matlab_bgl包中
 Perl：Graph组件下
 Python：SciPy库下（scipy.sparse.csgraph），库中也有
 R：e1071和Rfast包内

参考来源

参见 
 图论最短路
 Dijkstra算法
 Bellman-Ford算法

图算法
多项式时间问题
带有伪代码示例的条目