Floyd-Warshall算法
![本页使用了标题或全文手工转换](https://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
Floyd-Warshall | |
---|---|
图 | |
复杂 | |
图 |
---|
|
|
Floyd-Warshall
Floyd-Warshall
原理
[编辑]设为从
若 最短 路 径 经过点 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) (英 语).
参 见
[编辑]
|