侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

最短路径的实现算法(二):弗洛伊德算法(Floyd)

kaixindeken
2021-04-23 / 0 评论 / 0 点赞 / 99 阅读 / 443 字

实现原理

弗洛伊德算法的基本思想如下:

从任意节点 A 到任意节点 B 的最短路径不外乎两种可能,一种是直接从 A 到 B,一种是从 A 经过若干个节点到 B,所以,我们假设 dist(A,B) 为节点 A 到节点 B 的最短路径的距离,对于每一个节点 K,我们检查 dist(A,K) + dist(K,B) < dist(A,B) 是否成立,如果成立,证明从 A 到 K 再到 B 的路径比 A 直接到 B 的路径短,我们便设置 dist(A,B) = dist(A,K) + dist(K,B),这样一来,当我们遍历完所有节点 K,dist(A,B) 中记录的便是 A 到 B 的最短路径的距离。

算法复杂度

弗洛伊德算法实现包含三层循环,对应的算法时间复杂度也是 O(n3),但是实现起来更简单,适用于需要计算所有顶点间的最短路径这种场景;迪杰斯特拉还可以计算指定顶点到其他顶点的最短路径,时间复杂度只有 O(n2),所以这种情况下使用迪杰斯特拉算法更合适。

0

评论区