经典Bellman-Ford 算法，一文讲清｜老宋啃《算法导论》的笔记04

2165

2022.12.15

发布于未知归属地

被我记错的复杂度😵🤦‍♂️
重新学习📚
1. 前置概念和引理🔑
2. 算法过程描述📖
一道模板型例题，不要错过
例题代码：正确的和错误的
1. 错误代码❌
2. 正确代码✅
正确性证明🙆‍♂✍️
问答❓
扩展👣

被我记错的复杂度😵🤦‍♂️

在温习Bellman-Ford算法。

2022年11月27日晚上，系统地重新啃了一遍《算法导论》中的 Bellman-Ford 和 Dijkstra 两个单源最短路径算法。说来惭愧，本来想着乘热打铁，赶紧找几道例题练练手，防止遗忘，但这么多天过去了（今天已经是12月8日了），这个任务还没有完成。

每天确实很忙，但是产出很低。所做的工作不能说没意义，但是总是偏离目标。每天设立小目标还是很重要的，不能想做什么做什么。

今天终于开始着手 Bellman-Ford 算法，但是发现又忘了。凭借着残存的记忆，躺在床上努力在脑海中对其重新构建，发现很艰难。

我能记得，这个算法适用于带负权重的图，能够发现图中的负环，但是复杂度比 Dijkstra 算法高。我还朦朦胧胧记得其复杂度貌似是 $O (V^{2})$ ，但绝对不可能是 $O (E^{2})$ ，这里的 V、E 代表图的顶点集和边集的大小。因为，考虑到 $∣ E ∣$ 的上界是 $O (V^{2})$ ，假如 Bellman-Ford 算法复杂度是 $O (E^{2})$ ，其上界高达 $O (V^{4})$ ，这显然太夸张了，绝对不可能。

以这个复杂度为基点，我继续躺在床上用想象重现这个算法，脑中闪现过一些记忆碎片，比如"松弛操作"、各种《算法导论》那一章提到的引理，但是怎么也重现不了。

之所以逼着自己重现，是为了发掘模糊点、错漏点，以便复习时加深印象，更加有的放矢。

没办法，我只能重新把书看了一遍。

然后我发现，复杂度并不是 $O (V^{2})$ ，而是 $O (V E)$ 。尴尬🤣。这所以这么尴尬，还是对原理没掌握。从现在开始，我一定把这个时间复杂度焊死在脑子里。

来颗狗头缓解尴尬

重新学习📚

前置概念和引理🔑

负环：负环是有向中的一种特殊环路，这个环路上所有边的权重之和为负数。由于可以沿着负环走任意圈，假如一个顶点s可以到达这个负环，则s到这个负环中的任一个顶点，都不存在最小路径。

松弛操作：暂时略过。

相关引理：暂时略过。

略去的内容，暂时不影响对剩下内容的理解，如果想知道，详见《算法导论第24章》那些稀奇古怪的引理。

算法过程描述📖

Bellman-Ford算法的过程如下：

初始化。初始化起始点 $s$ 到每个其他顶点 $v$ 的预估最短路径 $d$ 为 $v . d = \infty$ ， $s$ 到自身的预估最短路径为 $s . d = 0$ 。
松弛。遍历图的边集 $∣ V ∣ - 1$ 次，每次遍历时都对每条边进行松弛操作。所谓松弛操作，就是对于边 $⟨ u, v ⟩$ ，如果 $v . d < u . d + w (u, v)$ ，则更新 $v . d$ 为 $u . d + w (u, v)$ 。其中， $w (u, v)$ 代表边 $⟨ u, v ⟩$ 的权重。这里要注意， $\infty$ 加上一个有限数，和依然被认为是 $\infty$ 。
负环检测。额外再遍历一次边集，对于某条边 $⟨ u, v ⟩$ ，如果 $v . d > u . d + w (u, v)$ ，则说明图中存在起始点 $s$ 可以到达的负环，算法直接返回false。
返回 true，代表没发现 $s$ 可以到达的负环，此时，每个顶点的 $d$ 值就是 $s$ 到它的最短路径。 $u . d = \infty$ 代表 $s$ 无法到达顶点 $u$ 。

从这个算法描述中，可以很容易看出其时间复杂度为 $O (V E)$ 。

这个算法并不难实现，但是真实写起来，还是有很多细节要注意的。

一道模板型例题，不要错过

leetcode 里没有找到涉及负环的题目，最后我在洛谷中找到了一道：P3385 【模板】负环。公众号不能放外链，读者可以点击文末的阅读全文找到这道题，或者自己复制 url 到浏览器中查看。

这里简单说一下洛谷这个网站。它是我发求助贴才知道的，也是一个刷题网站。非常感谢热心的大佬@rui_er。

这个网站在交互体验上，和 leetcode 有很多的不同，一开始会很不习惯。

洛谷最让我痛苦的是，必须自己从输入流中解析测试用例，并且算法的输出都是靠刷题者自己打印在控制台中。一开始，会感觉这种形式真的太可怕了，完全无法专注于算法本身。不过习惯就好。

其次就是，代码没有通过时，新用户无法找到出错的测试用例，即便绑定了手机号，完成了所谓的实名认证，依然不行。我只能反复地检查代码，小心地再次提交，前后折腾了不下 30 次。和这种地狱模式相比，leetcode 对新用户简直不要太友好。

比如我提交的过程中，下图红色的这一块 WA(代表 wrong answer)，真的很难排查，想让我撞墙。

洛谷的调试对我是一场噩梦 `

第三，洛谷只能看到题解，无法看到其他人 AC 了的代码。但是大部分题解貌似都是用 c 或者 python 写的。

第四，洛谷必须自己引入依赖的所有包，而不是像 leetcode 那样自动引入了常见的包。

第五，用 java 提交代码时，类名必须叫Main，否则无法执行。

最后，洛谷有很多规矩和行业黑话，感觉使用的时候要特别小心，否则很容易触犯天条，被处罚，被纠分。这些天条，我还没有来得及详细消化🤣。

例题代码：正确的和错误的

错误代码❌

我尝试了好多次，才在洛谷中通过了这道例题。在前后不下 30 次错误提交中，大多数是因为我解析测试数据异常，还有一次是因为审题错误，一定要仔细阅读这道题，题中没字是多余的，千万不能想当然。

再通过层层关卡和磨难后，我终于可以聚焦到 Bellman-Ford 算法本身上了，但有一个未知测试点终无法通过（见前图）：

import java.util.*;
/**
 * Bellman-Ford算法的错误形式 1
 */

public class Main{
    /**
     * 如果存在从s能到达的负环，返回true。注意，光有负环还不行，必须是能从 s 到达的负环。
     * @param s 起始节点
     * @param n 顶点数，所有的顶点大小都在闭合区间[1, n]内
     * @param edges 边的列表
     * @return
     */
    public static boolean bellmanFord(int s, int n, List<int[]> edges){
        int inf = Integer.MAX_VALUE;
        int[] ret = new int[n + 1];
        Arrays.fill(ret, inf);
        ret[s] = 0;
        while(n-- >= 2){
            for(int[] e: edges){
                int u = e[0], v = e[1], w = e[2];
                if(ret[u] == inf)continue;
                int d = ret[u] + w;
                if(d < ret[v])ret[v] = d;
            }
        }
        for(int[] e: edges){
            int u = e[0], v = e[1], w = e[2];
            if(ret[u] + w < ret[v])return false;
        }
        return true;
    }

    // 从输入中读取测试数据，然后调用 Bellman-Ford 算法
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- >= 1){
            List<int[]> edges = new ArrayList<>();
            int n = sc.nextInt(), m = sc.nextInt(); //n、m分别为点数和边数
            for(int i = 1; i <= m; i++){
                int[] e = new int[]{sc.nextInt(), sc.nextInt(), sc.nextInt()};
                edges.add(e);
                if(e[2] >= 0){
                    edges.add(new int[]{e[1], e[0], e[2]});
                }
            }
            System.out.println(bellmanFord(1, n, edges) ? "NO" : "YES");
        }
        sc.close();
    }
}

因为看不到那个测试点的数据，我把这段代码读了又读，自己在 IDEA 中构造了好多数据来调试，都没问题。一开始，我怀疑是不是测试数据中有自环。但是思考后我认为Bellman-Ford 算法完全适用有自环的情况。

然后我怀疑是 int 溢出了，尽管从题目中给出的数据范围看，即便把所有边的权重按照最大值加起来，也不会溢出。但是我依然还是把 int 改成 long 尝试了一遍，依然无果。

最后，又读了 N 遍代码，终于发现了隐藏的魔鬼。我没有在最后一个循环中，对正无穷+∞做处理，也就是下面代码中注释掉的那一句：

public class Main {
    public static boolean bellmanFord(int s, int n, List<int[]> edges) {
        // …………
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            // 这里不能落了这一句：if(ret[u] == inf)continue;
            if (ret[u] + w < ret[v]) return false;
        }
        return true;
    }
  
    //………
}

这一句确实很关键，因为是将Integer.MAX_VALUE当做正无穷+∞的。在 Bellman-Ford 算法中，默认会认为正无穷+∞加上或减去一个普通数，还是正无穷+∞。但使用Integer.MAX_VALUE做正无穷大，如果在其基础上再加一个正数，就会发生整数溢出。实际编码时，是否正确处理正无穷，是 Bellman-Ford 算法特别容易出错的一个点。

除了用Integer.MAX_VALUE，还可以用16进制数0x3f3f3f3f代表无穷大，据说搞算法竞赛的大佬们尤其喜欢这样。leetcode 里的灵茶山艾府大佬的昵称，就来自这个数。

0x3f3f3f3f的 10 进制数是1061109567，这是一个 10 亿级别的数字；Integer.MAX_VALUE，也就是 32 位正整数的最大值，是2147483647，所以0x3f3f3f3f乘以 2，依然还是小于Integer.MAX_VALUE。

所以0x3f3f3f3f作为一个足够大的整数，在其基础上再加一个数，通常不会发生整除溢出，很好地满足了正无穷加上一个正数还是正无穷这个性质。

尽管如此，在 Bellman-Ford算法中，使用0x3f3f3f3f作为正无穷大，还是不能滥用，因为在这个算法中，是允许负权重的，并且认为正无穷减去一个数字，依然还是正无穷。比如下面的代码就是错误的：

import java.util.*;
/**
 * Bellman-Ford算法的错误形式 2
 */
public class Main{
    /**
     * 如果存在从s能到达的负环，返回true。注意，光有负环还不行，必须是从s能到达的负环。
     * @param s 起始节点
     * @param n 顶点数，所有的顶点大小都在闭合区间[1, n]内
     * @param edges
     * @return
     */
    public static boolean bellmanFord(int s, int n, List<int[]> edges){
        int inf = 0x3f3f3f3f; //正无穷
        int[] ret = new int[n + 1];
        Arrays.fill(ret, inf);
        ret[s] = 0;
        while(n-- >= 2){
            for(int[] e: edges){
                int u = e[0], v = e[1], w = e[2];
                int d = ret[u] + w;
                //if(ret[u] == inf)continue;
                if(d < ret[v])ret[v] = d;
            }
        }
        for(int[] e: edges){
            int u = e[0], v = e[1], w = e[2];
            //if(ret[u] == inf)continue;
            if(ret[u] + w < ret[v])return false;
        }
        return true;
    }

    // 从输入中读取测试数据，然后调用 Bellman-Ford 算法
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- >= 1){
            List<int[]> edges = new ArrayList<>();
            int n = sc.nextInt(), m = sc.nextInt(); //n、m分别为点数和边数
            for(int i = 1; i <= m; i++){
                int[] e = new int[]{sc.nextInt(), sc.nextInt(), sc.nextInt()};
                edges.add(e);
                if(e[2] >= 0){
                    edges.add(new int[]{e[1], e[0], e[2]});
                }

            }

            System.out.println(bellmanFord(1, n, edges) ? "NO" : "YES");
        }
        sc.close();
    }
}

正确代码✅

从现在开始，把下面的代码模板也焊死在脑子里：

import java.util.*;
public class Main{
    /**
     * 如果存在从s能到达的负环，返回true。注意，光有负环还不行。
     * @param s 起始节点
     * @param n 顶点数，所有的顶点大小都在闭合区间[1, n]内
     * @param edges
     * @return
     */
    public static boolean bellmanFord(int s, int n, List<int[]> edges){
        int inf = Integer.MAX_VALUE;
        int[] ret = new int[n + 1];
        Arrays.fill(ret, inf);
        ret[s] = 0;
        while(n-- >= 2){
            for(int[] e: edges){
                int u = e[0], v = e[1], w = e[2];
                if(ret[u] == inf)continue;
                int d = ret[u] + w;
                if(d < ret[v])ret[v] = d;
            }
        }
        for(int[] e: edges){
            int u = e[0], v = e[1], w = e[2];
            if(ret[u] == inf)continue;
            if(ret[u] + w < ret[v]){
                return false;
            }
        }
        return true;
    }

    // 从输入中读取测试数据，然后调用 Bellman-Ford 算法
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- >= 1){
            List<int[]> edges = new ArrayList<>();
            int n = sc.nextInt(), m = sc.nextInt(); //n、m分别为点数和边数
            for(int i = 1; i <= m; i++){
                int[] e = new int[]{sc.nextInt(), sc.nextInt(), sc.nextInt()};
                edges.add(e);
                if(e[2] >= 0){
                    edges.add(new int[]{e[1], e[0], e[2]});
                }

            }

            System.out.println(bellmanFord(1, n, edges) ? "NO" : "YES");
        }
        sc.close();
    }
}

正确性证明🙆‍♂✍️

《算法导论》原书中，对 Bellman-Ford 算法的证明属实有些可怕。证明主要用到一条叫做路径松弛性质的引理，这条引理，又依赖另一条引理，依赖的依赖又依赖一条别的引理……

依赖链实在太长，虽然每一条单独地看都不复杂，但是一旦综合起来看，会让人感觉感觉翻过高山还有大海，没有清晰的主线。原文中用了三页纸的篇幅，而且这三页纸还散落在不同的小章节里。

我把这些引理总结了一下，放在了这篇前文提到过的笔记里：《算法导论第24章》那些稀奇古怪的引理。读者可以不看这篇笔记，但是一定要搞清楚笔记里提到的那些性质。

站在实用主义的角度上，证明不重要，还不如背背模板。这确实是一种策略。但是，实用主义要不得，还是努力消化一下吧。

路径松弛性质这条引理，我用自己的话重新复述了一遍：

如果 $p = ⟨ v_{1}, v_{2}, v_{3}, \dots, v_{k} ⟩$ 是从起始点 $s = v_{1}$ 到节点 $v_{k}$ 的某条最短路径，对于该路径上的每一条边 $e_{i} = ⟨ v_{i}, v_{i + 1} ⟩$ ， $1 <= i <= k - 1$ ，如果 $e_{i}$ 是第 1 条边，或者 $e_{i}$ 在被松弛之前，它的前一条边 $e_{i - 1} = ⟨ v_{i - 1}, v_{i} ⟩$ 已经被松弛过了，那么必然有 $v_{k} . d = δ (s, v_{k})$ 。

也就是说，假设存在从起始点 $s = v_{1}$ 到节点 $v_{k}$ 的最短路径，不妨记这条路径为 $p = ⟨ v_{1}, v_{2}, v_{3}, \dots, v_{k} ⟩$ ；某个算法只要能保证其中的所有 $k - 1$ 条边，能够按顺序被松弛一遍，那这个算法最终一定能求出这条路径的大小，哪怕在这个松弛的顺序中，混入了任何对其他边和这 $k - 1$ 条边的松弛，都不会影响结果。

按照本文前面的描述，Bellman-Ford算法分成三个步骤：初始化、松弛、负环检测，如果已经忘记了，请拉倒前面再瞄一眼。

证明这个算法，分两种情况讨论：

不存在起点 $s$ 能到达的负环。
存在起点 $s$ 能到达的负环。

对于情况 1，又可以分成两种不同类型的顶点： $s$ 可以到达的和不能到达的，继续分类讨论。

根据路径松弛性质这条引理，可以断定：算法在第二步松弛完成后，只要起始点 $s$ 能到达顶点 $u$ ，则到 $u$ 的最短短路径必然已经被求出来了，等于 $u . d$ 。逻辑过程是：一条最短路径，最多只可能包含 $∣ V ∣ - 1$ 条边，算法的第二步松弛步总共进行了 $∣ V ∣ - 1$ 轮循环，每一轮都会对所有边进行松弛，自然也包含对这条假想的最短路径上的某条边的松弛；所以 $∣ V ∣ - 1$ 轮循环后，可以保障对于任何一条假想的最短路径，其上的每一条边都按顺序被松弛了一遍。

这个逻辑过程，暗含了非常丰富的细节：

这解释了，为什么算法的第二步必须进行 $∣ V ∣ - 1$ 轮循环，而不可以是更少轮，也没必要有更多轮。在每一轮中，遍历边集的顺序可以是任意的，并不能排除存在特殊的情况：必须在第 $∣ V ∣ - 1$ 轮的时候，才能访问到假想中的最短路径的最后一条边。
这也暗示着，Bellman-Ford 算法在某些情况下，可能非常低效，即便已经求出了所有的最短路径了，但是算法依然继续做了若干轮多余的循环。

对于情况 1，也就是不存在起点 $s$ 能到达的负环时，如果 s 到某个顶点 $u$ 是不连通的，则算法第二步松弛步结束后， $u . d$ 必然为无穷大，符合预期。这可以根据另一条叫做非路径性质的引理得出，引理很好理解，此处略。

对于情况 1，接下来，可以利用反证法轻松证明，算法第三步一定可以被跳过。算法的第三步，会遍历每一条边，不妨记任一条边为 $⟨ u, v ⟩$ ，如果 $s$ 可以到达 $v$ ，由于 $v . d$ 已经是最小路径了，不可能存在更小的，所以必然不可能有 $v . d > u . d + w (u, v)$ ；反之，如果 $s$ 到达不了 $v$ ，则必然也不可能到达 $u$ ，此时 $v . d = \infty$ ， $u . d = \infty$ ，必然也不可能有 $v . d > u . d + w (u, v)$ 。

于是，情况 1 得到证明。

接下来考虑情况 2：存在起点 $s$ 能到达的负环。依然还是用反证法。此时，算法的正确性转换为：在第三步一定能检测出负环。记 $s$ 能到达的负环为 $⟨ v_{1}, v_{1}, v_{3}, \dots, v_{k} ⟩$ ，其中 $s = v_{1} = v_{k}$ ，于是有：

i = 1 \sum k - 1 v_{i + 1} . d = i = 1 \sum k - 1 v_{i} . d (式 1)

因为是负环，环中边的权重和必然小于 0，于是有：

i = 1 \sum k - 1 w (v_{i}, v_{i + 1}) < 0 (式 2)

用反证法，假设第三步会被跳过，那么负环中的任一条边 $⟨ v_{i}, v_{i + 1} ⟩$ ，必然满足 $v_{i + 1} . d \leq v_{i} . d + w (v_{i}, v_{i + 1})$ ，对这个不等式两侧累加求和，得到：

i = 1 \sum k - 1 v_{i + 1} . d <= i = 1 \sum k - 1 v_{i} . d + i = 1 \sum k - 1 w (v_{i}, v_{i + 1}) (式 3)

仔细观察，将式 2 代入式 3，得到：

i = 1 \sum k - 1 v_{i + 1} . d < i = 1 \sum k - 1 v_{i} . d (式 4)

仔细观察，式 4 和式 1 相互矛盾，所以第三步肯定不会被跳过，情况 2 得证。

于是，经典 Bellman-Ford 算法得证。

我发现，《算法导论》中的很多证明，其实都是采用了分类讨论、反证法、数学归纳法。

问答❓

问：Bellman-Ford算法，适用于图中有自环的情况吗？

适用。从对Bellman-Ford算法的描述和证明过程看，自环不会对结果有任何影响，即便是权重为 0 的自环，也不会有影响。

问：Bellman-Ford算法求解最短路问题时，需要先生成邻接表或临接矩阵吗？

不需要，直接遍历边集即可，并且完全不必纠结边的顺序。

问：Bellman-Ford算法，能用来判断图中是否有负环吗？

能，但是有条件。Bellman-Ford算法，可以断言是否存在某个特定的起点 $s$ 是能到达的负环。换句话说，图中完全可能存在某个负环，但是起点 $s$ 到达不了这个环。可以先求出图的所有联通分量，然后在每个联通分量中挑选一个起始点，分别运行 Bellman-Ford 算法。

问：Bellman-Ford算法，可以求出图中所有的负环吗？

我不知道，我还没有研究过。但是我觉得应该可以。可以考虑在算法的第三步，检测到负环时不要返回，而是记录下相应的边。但是我不确定这样是否能行。

也可能存在别的更高效的方法。

扩展👣

Bellman-Ford 算法相关的知识点，实在太多了，本文写不下。这篇文章从 2022.11.27开始，已经拖拖拉拉写到今天2022.12.15日了🤣。

以上学习笔记，仅仅是关于经典 Bellman-Ford 算法的，基于《算法导论》。该算法还有很多变体。

实际刷题的时候，我发现 leetcode 中似乎很少有相关题目，也可能是我刷题数量还不够。leetcode 中涉及到的，多是 Bellman-Ford 算法的变体：限制最多走 k 步，求起点到某个顶点的最短路径。这也是《算法导论》中的一道思考题。

Bellman-Ford 算法，其实还可以从动态规划的角度来理解，尽管《算法导论》章节中没有提到这一点（也可能是我遗漏了没看全），并且本文中看不出任何动态规划的影子。事实上，我发现 leetcode 社区中，很多人认为 Bellman-Ford 算法就是一种动态规划算法。

确实，最短路径问题具有最优子结构性质，所以和动态规划和贪心算法剪不断理还乱。

Bellman-Ford 算法适用于带负权重的边，但是比较低效。为了减少冗余的遍历，很多人对Bellman-Ford 算法进行了优化。其中流传最广的的是Shortest Path Faster Algorithm (SPFA)，这个算法于1994年被中国人段凡丁重新发现并命名，现在在网上还能很多争吵，甚至有人认为 SPFA 已死。

这些扩展内容，以后再讲。