- 当前
- 已有距离
- 已用的边
- 路径
- 负环
贝尔曼-福特算法
当某条边的长度为负时,Dijkstra 算法就会失效,就像一条不收你过路费、反而付钱给你的路。Bellman–Ford 算法不会:它只是一遍又一遍地检查每条边,直到没有任何改进,甚至能发现某个环让距离无限下降。点击一个节点从那里开始,逐趟查看。 按“播放”观看搜索过程,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。每条边都是单向的,如箭头所示,边上的数字是它的长度,可以是负数。点击节点可将其设为起点;把点击切换为“终点”,再点击另一个节点,即可在最后看到到它的最短路径。每个节点上的数字是它目前的距离。勾选“加入负环”,看看 Bellman–Ford 算法如何找到负环。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。
它是如何运作的
- 点击一个节点设为起点。要在最后看到路径,把点击切换为“终点”,再点击另一个节点。
- 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到任意位置。
- 勾选“加入负环”,看 Bellman–Ford 算法如何找到它。“新图”会生成另一张图供你尝试。
Bellman–Ford 算法的工作原理
把起点的距离设为 0,其他节点设为无穷大。然后逐趟进行:每一趟把每条边 u → v 检查一次。如果 u 有距离,且 dist(u) 加上边长比 dist(v) 短,就降低 dist(v),并记下 u 作为到达那里的路线。第 k 趟之后,所有最多使用 k 条边的最短路径都已知道。最短路径每个节点最多经过一次,所以最多有 n − 1 条边,n − 1 趟总是足够。如果整整一趟没有任何改变,搜索可以提前停止。
寻找负环
如果一个环的边加起来小于零,再绕它一圈总能让路径更短,因此根本没有最短路径。Bellman–Ford 能发现这一点:n − 1 趟之后,再多一趟应该不会有任何改变。如果某条边仍能松弛,就说明从起点可以到达一个负环,从这条边沿着记下的节点往回走,就会进入这个环。在应用中,这个环画成红色。
常见问题
什么是 Bellman–Ford 算法?
一种求从一个起点到所有其他节点的最短路径的算法,适用于边长可以为负的图。它反复逐趟松弛每条边;如果从起点能到达负环,它会报告出来。
Dijkstra 算法为什么不能处理负权边?
Dijkstra 一旦发现某个节点是队列中最近的,就把它的距离确定下来。之后发现的负权边仍可能经由更短的路线回到那个节点,所以确定的距离可能是错的。Bellman–Ford 从不提前确定距离;它会一直检查每条边。
为什么是 n − 1 趟?
最短路径从不需要两次经过同一个节点,所以最多有 n − 1 条边。每一趟至少把已知的最短路径延长一条边,所以 n − 1 趟之后就全部找到了。
Bellman–Ford 算法有多快?
每一趟检查全部 E 条边,最多有 V − 1 趟,所以工作量按 V × E 增长。这比 Dijkstra 算法慢,所以 Bellman–Ford 只在边可能为负时使用。
我的图会被发送到别处吗?
不会。图在你的浏览器中生成和搜索,上次的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器