《我的第一本算法书》阅读笔记 4-4 贝尔曼 - 福特算法

蔚落 2022-10-22 06:28 238阅读 0赞

贝尔曼 - 福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径。

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

这里我们设A为起点、 G为终点，来讲解贝尔 曼-福特算法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

首先设置各个顶点的初始权重 ：起点为 0，其他顶点为无穷大（∞）。这个权重表示的是从 A 到该顶点的最短路径的暂定距离。随着计算往下进行，这个值会变得越来越小，最终收敛到正确的数值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

从所有的边中选出一条边，此处选择了连接 A-B 的边。然后，分别计算这条边从一端到另一端的权重， 计算方法是“顶点原本的权重＋边的权重”。只要按顺序分别计算两个方向的权重即可，从哪一端开始都没有问题。此处我们选择按顶点权重从小到大的方向开始计算。

![20210404194409385.png][]

A 的权重小于 B，因此先计算从 A 到 B 的权重。 A 的权重是 0，边 A-B 的权重是 9，因此 A 到 B 的权重是 0+9=9。

![20210404194552114.png][]

如果计算结果小于顶点的值，就更新这个值。 顶点B的权重是无穷大，比9大，所以把它更新为9。更新时需要记录计算的是从哪个顶点 到该顶点的路径。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

接下来计算从 B 到 A 的权重。B 的权重为 9，从 B 到 A 的权重便为 9+9=18。与顶点 A 现在的值 0 进行比较，因为现在的值更小，所以不更新。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

对所有的边都执行同样 的操作。在执行顺序上 没有特定要求，此处我 们选择从靠近左侧的边 开始计算。先选出一条 边……

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5][]

数值更新了，顶点C的权重变成了2

![20210404195419482.png][]

同样地，再选出一条边…

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6][]

权重又更新了。此时就能看出，从顶点A前往顶点B时，比起从A直达B，在C中转一次的权重更小。

![20210404201310733.png][]

接着对所有的边进行更新操作。

![20210404201459219.png][]

更新边 B-D 和边 B-E。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7][]

更新边 C-D 和边 C-F

更新完所有的边后，第1轮更新就结束了。接着，重 复对所有边的更新操作，直到权重不能被更新为止。

--------------------

![20210404201720409.png][]

第2轮更新也结束了。顶点B的权重从8变成了7，顶点E的权重从9变成了8。接着，再执 行一次更新操作。

![20210404201801296.png][]

第3轮更新结束，所有顶点的权重都不再更 新，操作到此为止。算法的搜索流程也就此结 束，我们找到了从起点到其余各个顶点的最短 路径。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8][]

根据搜索结果可知，从起点 A 到终点 G 的最短路径是 A-C-D-F-G，权重为 14

--------------------

将图的顶点数设为 n、边数设为 m，我们来思考一下贝尔曼 - 福特算法的时间复杂度是多少。该算法经过 n 轮更新操作后就会停止，而在每轮更新操作中都需要对各个边进行 1 次确认，因此 1 轮更新所花费的时间就是 O(m)，整体的时间复杂度就是 O(nm)。

为了便于说明，前面的讲解以无向图为例，但在有向图中同样可以求解最短路径问 题。选出一条边并计算顶点的权重时，无向图中的计算如前文步骤 03~06 所示，两个方向都要计算，而在有向图中只按照边所指向的那个方向来计算就可以了。

### 补充说明 ###

计算最短路径时，边的权重代表的通常都是时间、距离或者路费等，因此基本都是 非负数①。不过，即便权重为负，贝尔曼 - 福特算法也可以正常运行。

但是，如果在一个闭环中边的权重总和是负数，那么只要不断遍历这个闭环，路径 的权重就能不断减小，也就是说根本不存在最短路径。遇到这种对顶点进行 n 次更新操 作后仍能继续更新的情况，就可以直接认定它“不存在最短路径”。

另外，如果使用 4-5 节将会介绍的狄克斯特拉算法，那么当输入的权重为负时还有 可能无法得出正确的答案。

贝尔曼-福特算法的名称取自其创始人理查德·贝尔曼和莱斯特·福特的名字。贝尔曼也 因为提出了该算法中的一个重要分类“动态规划”而被世人所熟知。

--------------------

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/a2b685b603b5437aa21f48b78137ac75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/b71c075bcee0466db45ef15f72d5b334.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/2a2a8eea19e442d4ba7518fb1fd6ef8a.png
[20210404194409385.png]: /images/20221022/42c64ee201484aafbbf7bf3c1bf3640f.png
[20210404194552114.png]: /images/20221022/e46186eff8c1452dbc79e86cc2972eea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20221022/c5b25d27c1b8461088583538d0626e32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20221022/6da33609f4c047b688aaad619881f1ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5]: /images/20221022/c0c2ed0e2eab452e975f020d1f42dadf.png
[20210404195419482.png]: /images/20221022/273d514fb2974dad8389bb94a07e48cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6]: /images/20221022/79ca4c663024428b96699ae670c1cfce.png
[20210404201310733.png]: /images/20221022/d70780c2f5d7432f9f7e9151be6c01d5.png
[20210404201459219.png]: /images/20221022/abef23caf21e41a3803ce1ca2288c13a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7]: /images/20221022/9f0c5e7f5cd642d5a02b0235a5a0a4d7.png
[20210404201720409.png]: /images/20221022/11659cadd5c74adcafa2440effbaf44d.png
[20210404201801296.png]: /images/20221022/3e75d6210f3a4e2b911fcdf0545f8a94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8]: /images/20221022/9fda075bc888421796209fc8f76da21b.png