Floyd-Warshall算法

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

Floyd-Warshall算法
概况
类别	全局最短路径问题（适用于带权图）
数据结构	图
复杂度
平均时间复杂度	${\displaystyle \Theta (|V|^{3})}$
最坏时间复杂度	${\displaystyle O(|V|^{3})}$
最优时间复杂度	${\displaystyle \Omega (|V|^{3})}$
空间复杂度	${\displaystyle \Theta (|V|^{2})}$
相关变量的定义
${\displaystyle V}$	点集

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

原理

Floyd-Warshall算法的原理是动态规划^[5]。

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

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

因此，${\displaystyle 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]表示由点${\displaystyle i}$到点${\displaystyle j}$的代价，当其为 ∞ 表示两点之间没有任何连接。

使用动态规划的算法

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

实现

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

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

参考来源

1. 杨军庆、安容瑾、任志国、张潇赟、蔡晓龙. 基于佛洛依德算法的各院校间最短路径问题的求解. 《甘肃科技纵横》. 2010年, (5): 28-29 [2020-08-09]. （原始内容存档于2011-02-24）.
2. Stefan Hougardy. The Floyd–Warshall algorithm on graphs with negative cycles. Information Processing Letters. 2010年4月, 110 (8-9): 279–281 [2015-04-11]. doi:10.1016/j.ipl.2010.02.001. （原始内容存档于2015-09-24） （英语）.
3. Skiena, Steven. The Algorithm Design Manual (PDF) 2. Springer. 2008-07-26: 212 [2015-04-11]. ISBN 978-0073523408. doi:10.1007/978-1-84800-070-4. （原始内容 (PDF)存档于2015-06-09） （英语）.
4. Introduction to Algorithms [算法导论]. 机械工业出版社. 2006: 386 [2001]. ISBN 9787111187776 （中文（中国大陆））.
5. Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh. Algorithms (PDF) 1. McGraw-Hill Science/Engineering/Math. 2006-09-13: 176 [2015-04-11]. ISBN 978-0073523408. （原始内容 (PDF)存档于2015-02-13） （英语）.

参见

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