Floyd-Warshall算法

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

Floyd-Warshall算法

Floyd-Warshall算法 -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}- 算法（），中文亦称弗洛伊德算法或佛洛依德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包。算法的时间复杂度为formula_1，空间复杂度为formula_2，其中formula_3是点集。原理. 算法的原理是动态规划。设formula_4为从formula_5到formula_6的只以formula_7集合中的节点为中间节点的最短路径的长度。因此，formula_10。在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。算法描述. 算法的伪代码描述如下： 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 其中codice_1表示由点formula_5到点formula_6的代价，当其为 ∞ 表示两点之间没有任何连接。实现. Floyd算法在不同的编程语言中均有大量的实现方法：

威廉·亨利·皮克林

禾本科

赵松庭

宋庆龄

计算生物学

杨虎城

毛人凤

童话

版画

十四行诗

小麦

理发师悖论