Floyd–Warshall 算法
旧式公路地图册的最后有一张表:每两座城市之间的距离。Floyd–Warshall 算法就是计算这种表的方法,也是有史以来最短的算法之一:三重循环、一次比较,所有最短距离就各就各位。
基本思路
Dijkstra 算法和 Bellman–Ford 算法求的是从一个起点出发的最短距离。Floyd–Warshall 算法则一次求出从每个节点到其他每个节点的最短距离,结果放在一张表中,每个节点占一行一列。它从边直接给出的信息开始,然后允许越来越多的节点作为途中的中转点,逐步改进整张表。
逐步过程
填表:每个节点到自身为 0,相邻节点之间为边的长度,其他为无穷大。然后,对每个节点 k,以及每对 i、j:如果 i 到 k 的距离加 k 到 j 的距离小于 i 到 j 的距离,就写入较小的数。整个算法就是这些。写成代码是三重循环,k 在最外层。
一个例子
取四个节点,边为 A–B 长 3、B–C 长 1、A–C 长 5、C–D 长 2。表格从这些边开始,A–D 和 B–D 为无穷大。A 这一轮没有变化,因为经过 A 的路线都更长。B 这一轮找到 A 经由 B 到 C:3 + 1 = 4,比 5 短。C 这一轮找到 A 经由 C 到 D:4 + 2 = 6,以及 B 到 D:1 + 2 = 3,都是第一次找到的路线。D 这一轮没有变化。最终的表:A–B 3、A–C 4、A–D 6、B–C 1、B–D 3、C–D 2。
为什么循环顺序很重要
中转点 k 必须是最外层循环。k 这一轮结束后,每一项都是只用前 k 个节点作中转点时的最短距离,下一轮在此基础上进行:经过新中转点的最佳路径,就是到它的最佳路径加上从它出发的最佳路径,两者都已正确。把 k 放在内层循环会破坏这一保证,可能留下错误的距离。在一轮中直接原地更新表格是安全的,因为 k 本身的行和列在这一轮中不会改变。
历史与用途
Bernard Roy 于 1959 年描述了这种方法。1962 年,Stephen Warshall 将它用于传递闭包发表(传递闭包只问一个节点能否到达另一个节点),Robert Floyd 将它用于最短路径发表。它可以计算距离表和路由表,求出网络的直径,判断哪些节点能到达哪些节点,对角线上出现负数时还能发现负环。
动手探索
打开应用,按“单步”。一边是图,另一边是表格。每一轮会高亮当前中转点的行和列;每一步写入一对节点的更短距离,并给相加的两项加上边框。本轮变化过的格子会着色。选择起点和终点,表格完成后即可看到两者之间的最短路径。
常见问题
Floyd–Warshall 算法的时间复杂度是多少?
n 个节点时为 O(n³),与边数无关,表格需要 O(n²) 内存。对于小图或稠密图,它是首选方法,简单的循环运行得非常快。
用 Floyd–Warshall 算法,还是从每个节点运行 Dijkstra 算法?
对于稠密图,或边可能为负时,Floyd–Warshall 算法更简单,速度也差不多。对于边非负的大型稀疏图,从每个节点运行 Dijkstra 算法更快。
Floyd–Warshall 算法是动态规划吗?
是的。它利用前 k − 1 个节点的答案,求解中转点在前 k 个节点中的路径问题,而且只保留一张表,边算边覆盖。
什么是传递闭包?
一张只记录哪些节点能到达哪些节点、不管距离的表。Warshall 版本的算法用“或”和“与”代替“min”和“+”来计算它。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试 Floyd–Warshall 算法