Floyd-Warshall算法
Floyd-Warshall算法(英语:Floyd-Warshall algorithm),中文亦称弗洛伊德算法或佛洛依德算法[1],是解决任意两点间的最短路径的一种算法[2],可以正确处理有向图或负权(但不可存在负权回路)的最短路径问题,同时也被用于计算有向图的传递闭包[3]。
Floyd-Warshall算法 | |
---|---|
概况 | |
类别 | 全局最短路径问题(适用于带权图) |
数据结构 | 图 |
复杂度 | |
平均时间复杂度 | |
最坏时间复杂度 | |
最优时间复杂度 | |
空间复杂度 | |
相关变量的定义 | |
点集 |
原理
Floyd-Warshall算法的原理是动态规划[5]。
设 为从 到 的只以 集合中的节点为中间节点的最短路径的长度。
- 若最短路径经过点k,则 ;
- 若最短路径不经过点k,则 。
因此, 。
在实际算法中,为了节约空间,可以直接在原来空间上进行迭代,这样空间可降至二维。
算法描述
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]
表示由点 到点 的代价,当其为 ∞ 表示两点之间没有任何连接。
使用动态规划的算法
实现
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(页面存档备份,存于互联网档案馆)包内
参考来源
- ^ 杨军庆、安容瑾、任志国、张潇赟、蔡晓龙. 基于佛洛依德算法的各院校间最短路径问题的求解. 《甘肃科技纵横》. 2010年, (5): 28-29 [2020-08-09]. (原始内容存档于2011-02-24).
- ^ 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) (英语).
- ^ 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) (英语).
- ^ Introduction to Algorithms [算法导论]. 机械工业出版社. 2006: 386 [2001]. ISBN 9787111187776 (中文(中国大陆)).
- ^ 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算法