Floyd-Warshall算法

Floyd-Warshall算法
分类 全局最短路径问题(适用于带权图)
数据结构
最坏时间复杂度
最优时间复杂度
空间复杂度

Floyd-Warshall算法英语:Floyd-Warshall algorithm),中文亦称弗洛伊德算法,是解决任意两点间的 最短路径的一种 算法 [1],可以正確處理 有向圖或负权(但不可存在负权回路)的最短路径問題,同时也被用于计算有向图的传递闭包 [2]

Floyd-Warshall算法的 时间复杂度 [3]空间复杂度

原理

Floyd-Warshall算法的原理是 动态规划 [4]

为从的只以集合中的节点为中间節点的最短路径的长度。

  1. 若最短路径经过点k,则
  2. 若最短路径不经过点k,则

因此,

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

其他语言