中转点
已缩短的节点对
已检查的节点对

  • 当前中转点
  • 已是中转点
  • 缩短的节点对
  • 路径
点击节点设为

更多关于 Floyd–Warshall 算法

Floyd–Warshall 算法

从每个城镇到其他每个城镇有多远?Floyd–Warshall 算法用一张表和三重循环一次给出答案。每一轮多允许一个节点作为途中的中转点,并对每一对节点检查绕经它是否更短。单步查看表格如何填满、距离如何下降。 按“播放”观看表格逐步填满,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。表格记录目前找到的每对节点之间的最短距离;每条边上的数字是它的长度。每一轮多允许一个节点作为途中的中转点,每一步显示一对经由它变短的节点。点击节点可将其设为起点;把点击切换为“终点”,再点击另一个节点,即可在最后看到两者之间的最短路径。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。

它是如何运作的

  1. 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到任意位置。
  2. 观察表格:当前中转点的行和列会着色,每一步写入一个更短的距离。
  3. 选择起点和终点,可在最后看到两者之间的最短路径。“新图”会生成另一张图供你尝试。

Floyd–Warshall 算法如何工作

建一张表,每个节点占一行一列。对角线填 0,两个节点有边相连处填边的长度,其他地方填无穷大。然后依次把每个节点 k 当作可能的中转点。对每对 i、j,比较表中 i 到 j 的距离与 i 到 k 的距离加 k 到 j 的距离,保留较小者。处理完最后一个节点后,每一项都是其两个节点之间的最短距离。

为什么可行

k 这一轮结束后,表格对每一对节点记录的是中转点全都在已处理节点中的最短路径。下一个节点的这一轮只需判断该节点是否有帮助:经过它的最短路径,就是到它的最短路径加上从它出发的最短路径,两者都已在表中。这种用已求出的较小答案构建大答案的方法叫作动态规划。有负权边时它仍然有效,对角线上出现负数则说明存在负环。

常见问题

什么是 Floyd–Warshall 算法?

一种求出加权图中每对节点之间最短距离的算法。它维护一张距离表,并依次对每个节点检查:经过该节点能否让某对节点的距离变短。

Floyd–Warshall 算法有多快?

它对 n 个节点有三重循环,所以工作量随 n³ 增长,表格需要 n² 项。对几百个节点的图没有问题。对于大型稀疏图,从每个节点各运行一次 Dijkstra 算法更快。

Floyd–Warshall 算法能处理负权边吗?

能,只要没有负环。如果有负环,对角线上会有某一项变为负数,Floyd–Warshall 算法正是这样检测出负环的。

怎样得到路径,而不只是距离?

再维护一张表,记录从 i 到 j 途中的下一个节点。每当某对节点经由 k 变短时,就复制从 i 走向 k 的下一个节点。从 i 沿着这张表走到 j,就得到整条路径。

我的图会被发送到别处吗?

不会。图的生成和表格的填写都在你的浏览器中完成,上次的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器