代码随想录算法训练营第61天 | 图论part10：Bellman_ford 队列优化算法、bellman_ford之判断负权回路、bellman_ford之单源有限最短路

第十一章：图论part10

今天大家会感受到 Bellman_ford 算法系列在不同场景下的应用。
建议依然是：一刷的时候，能理解原理，知道Bellman_ford 解决不同场景的问题，照着代码随想录能抄下来代码就好，就算达标。
二刷的时候自己尝试独立去写，三刷的时候才能有一定深度理解各个最短路算法。

Bellman_ford 队列优化算法（又名SPFA）

文章讲解

思路

Bellman_ford 算法每次松弛都是对所有边进行松弛。但真正有效的松弛，是基于已经计算过的节点在做的松弛。

image.png

本图中，对所有边进行松弛，真正有效的松弛，只有松弛边（节点1->节点2）和边（节点1->节点3）。而松弛边（节点4->节点6），边（节点5->节点3）等等都是无效的操作，因为节点4 和节点 5 都是没有被计算过的节点。

只需要对上一次松弛的时候更新过的节点作为出发节点所连接的边进行松弛就够了。
基于以上思路，用队列来记录（其实用栈也行，对元素顺序没有要求）上次松弛的时候更新过的节点。

1. 模拟过程

初始化：从起点开始，minDist[start] 设置为 0，表示起点到自身的距离为 0，其他节点初始化为 INT_MAX，表示无限远。将起点节点加入队列。
松弛操作：
1. 从队列中取出一个节点 node，松弛所有从 node 出发的边。
2. 如果通过 node 到达某个节点 to 的路径更短，则更新 minDist[to]，并将 to 节点加入队列。
3. 重复以上步骤，直到队列为空。
终止条件：当所有节点的最短路径都已经确定，且队列为空时，算法结束。

2. Java 代码实现

以下是实现 SPFA（队列优化版 Bellman-Ford）算法的 Java 代码：

import java.util.*;

class Edge {
    int to, val;

    Edge(int to, int val) {
        this.to = to;
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 节点数量
        int m = sc.nextInt(); // 边数量

        // 邻接表表示图
        List<List<Edge>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 记录是否在队列中的数组
        boolean[] isInQueue = new boolean[n + 1];

        // 读取所有边并存储在邻接表中
        for (int i = 0; i < m; i++) {
            int p1 = sc.nextInt();
            int p2 = sc.nextInt();
            int val = sc.nextInt();
            graph.get(p1).add(new Edge(p2, val));
        }

        int start = 1;  // 起点
        int end = n;    // 终点

        // 最短路径数组，初始化为最大值
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[start] = 0;

        // 队列初始化，并将起点加入队列
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        isInQueue[start] = true;

        // SPFA主循环
        while (!queue.isEmpty()) {
            int node = queue.poll();
            isInQueue[node] = false;

            // 遍历所有从当前节点出发的边，尝试松弛
            for (Edge edge : graph.get(node)) {
                int to = edge.to;
                int value = edge.val;

                // 如果通过node到to的距离更短，更新minDist[to]
                if (minDist[to] > minDist[node] + value) {
                    minDist[to] = minDist[node] + value;

                    // 如果to不在队列中，则将其加入队列
                    if (!isInQueue[to]) {
                        queue.offer(to);
                        isInQueue[to] = true;
                    }
                }
            }
        }

        // 输出结果
        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.println("unconnected"); // 不能到达终点
        } else {
            System.out.println(minDist[end]); // 到达终点最短路径
        }

        sc.close();
    }
}

3. 模拟过程举例

以下是基于上述代码的模拟过程，以题目中的示例输入为例：

示例输入：

步骤解析：

初始化：
- minDist[1] = 0（起点到自身的距离为 0），其他节点 minDist 为 Integer.MAX_VALUE。
- 将起点节点 1 加入队列。
第一轮松弛：
- 从队列中取出节点 1，松弛边 1 -> 2 和 1 -> 3：
  - 更新 minDist[2] = 1，将节点 2 加入队列。
  - 更新 minDist[3] = 5，将节点 3 加入队列。
第二轮松弛：
- 从队列中取出节点 2，松弛边 2 -> 5 和 2 -> 4：
  - 更新 minDist[5] = 3，将节点 5 加入队列。
  - 更新 minDist[4] = -2，将节点 4 加入队列。
第三轮松弛：
- 从队列中取出节点 3，但没有新的边可以松弛，继续下一个节点。
第四轮松弛：
- 从队列中取出节点 4，松弛边 4 -> 6：
  - 更新 minDist[6] = 2，将节点 6 加入队列。
第五轮松弛：
- 从队列中取出节点 5，松弛边 5 -> 3 和 5 -> 6：
  - 更新 minDist[3] = 4，节点 3 已在队列中，不用再加入。
  - 更新 minDist[6] = 1。
第六轮松弛：
- 从队列中取出节点 6，没有新的边可以松弛。
- 最后，队列为空，算法结束。

最终结果：

输出最短路径 minDist[6]，即 1。

4. 效率分析

理论时间复杂度：SPFA 的时间复杂度依赖于图的稠密度，最坏情况下为 O(N * E)，但一般情况下时间复杂度为 O(K * N)，其中 K 取决于图的稠密度。
实践性能：SPFA 的实际运行时间还受制于队列操作的效率，特别是在稠密图中，队列操作的频繁调用可能导致时间消耗增加。

5. 拓展

正权回路：SPFA 在正权回路中表现稳定，不会陷入死循环，最终总会收敛到最短路径结果。
负权回路：如果图中存在负权回路，需要特别处理，否则可能导致无限循环。

bellman_ford之判断负权回路

文章讲解

思路

本题是要我们判断负权回路，也就是图中出现环且环上的边总权值为负数。如果在这样的图中求最短路的话，就会在这个环里无限循环（也是负数+负数只会越来越小），无法求出最短路径。所以对于在有负权值的图中求最短路，都需要先看看这个图里有没有负权回路。
解决本题的核心思路，就是在 kama94.城市间货物运输I 的基础上，再多松弛一次，看minDist数组是否发生变化。

代码实现

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 节点数量
        int m = sc.nextInt(); // 边的数量

        List<int[]> grid = new ArrayList<>();

        // 读取所有边的信息
        for (int i = 0; i < m; i++) {
            int p1 = sc.nextInt();
            int p2 = sc.nextInt();
            int val = sc.nextInt();
            // p1 指向 p2，权值为 val
            grid.add(new int[]{p1, p2, val});
        }

        int start = 1;  // 起点
        int end = n;    // 终点

        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[start] = 0;

        boolean flag = false;

        // 进行 n 次松弛操作，最后一次用于检测负权回路
        for (int i = 1; i <= n; i++) {
            for (int[] side : grid) {
                int from = side[0];
                int to = side[1];
                int price = side[2];
                if (i < n) {
                    if (minDist[from] != Integer.MAX_VALUE && minDist[to] > minDist[from] + price) {
                        minDist[to] = minDist[from] + price;
                    }
                } else { // 第 n 次松弛，用于检测负权回路
                    if (minDist[from] != Integer.MAX_VALUE && minDist[to] > minDist[from] + price) {
                        flag = true;
                    }
                }
            }
        }

        if (flag) {
            System.out.println("circle"); // 存在负权回路
        } else if (minDist[end] == Integer.MAX_VALUE) {
            System.out.println("unconnected"); // 终点无法到达
        } else {
            System.out.println(minDist[end]); // 输出最短路径
        }

        sc.close();
    }
}

代码解释

输入处理：
- n 为节点数量，m 为边的数量。
- 使用 List<int[]> 来存储边的信息，其中 int[] 数组表示一条边，包含三个元素 [p1, p2, val]，表示从节点 p1 到节点 p2 的边，权值为 val。
初始化：
- minDist 数组用于存储从起点到各个节点的最短距离，初始化为 Integer.MAX_VALUE（相当于 C++ 中的 INT_MAX），表示无穷大。
- minDist[start] 设置为 0，表示起点到自身的距离为 0。
松弛操作：
- 进行 n 次松弛操作，最后一次（即第 n 次）松弛用于检测负权回路。
- 每次松弛遍历所有边，如果通过当前边能够找到更短的路径，则更新 minDist 数组。
检测负权回路：
- 如果在第 n 次松弛操作中，某个节点的最短距离仍然可以更新，说明存在负权回路。
结果输出：
- 如果存在负权回路，输出 "circle"。
- 如果 minDist[end] 仍然是 Integer.MAX_VALUE，说明终点无法到达，输出 "unconnected"。
- 否则输出起点到终点的最短路径值。

时间复杂度和空间复杂度

时间复杂度：O(N * E)，其中 N 为节点数量，E 为图中边的数量。
空间复杂度：O(N)，主要用于存储 minDist 数组。

拓展：使用队列优化版的bellman_ford

代码实现

import java.util.*;

class Edge {
    int to, val;

    Edge(int to, int val) {
        this.to = to;
        this.val = val;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 节点数量
        int m = sc.nextInt(); // 边的数量

        List<List<Edge>> grid = new ArrayList<>(n + 1); // 邻接表
        for (int i = 0; i <= n; i++) {
            grid.add(new ArrayList<>());
        }

        // 将所有边保存起来
        for (int i = 0; i < m; i++) {
            int p1 = sc.nextInt();
            int p2 = sc.nextInt();
            int val = sc.nextInt();
            // p1 指向 p2，权值为 val
            grid.get(p1).add(new Edge(p2, val));
        }

        int start = 1;  // 起点
        int end = n;    // 终点

        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[start] = 0;

        Queue<Integer> que = new LinkedList<>();
        que.offer(start); // 队列里放入起点 

        int[] count = new int[n + 1]; // 记录节点加入队列的次数
        count[start]++;

        boolean flag = false;
        while (!que.isEmpty()) {

            int node = que.poll();

            for (Edge edge : grid.get(node)) {
                int from = node;
                int to = edge.to;
                int value = edge.val;

                if (minDist[to] > minDist[from] + value) { // 开始松弛
                    minDist[to] = minDist[from] + value;
                    que.offer(to);
                    count[to]++;
                    if (count[to] == n) { // 如果加入队列次数超过 n-1 次，就说明该图存在负权回路
                        flag = true;
                        que.clear(); // 清空队列，跳出循环
                        break;
                    }
                }
            }
        }

        if (flag) {
            System.out.println("circle"); // 存在负权回路
        } else if (minDist[end] == Integer.MAX_VALUE) {
            System.out.println("unconnected"); // 终点无法到达
        } else {
            System.out.println(minDist[end]); // 输出最短路径
        }

        sc.close();
    }
}

代码解析

输入处理：
- n 为节点数量，m 为边的数量。
- 使用 List<List<Edge>> 来构建图的邻接表，每个节点对应一个 List<Edge> 来存储与其相连的边。
初始化：
- minDist 数组用于存储从起点到各个节点的最短距离，初始化为 Integer.MAX_VALUE（相当于 C++ 中的 INT_MAX），表示无穷大。
- count 数组用于记录每个节点进入队列的次数，初始化为 0。
SPFA 主循环：
- 将起点节点 start 加入队列，并开始循环松弛操作。
- 每次从队列中取出一个节点 node，松弛所有与其相连的边。
- 如果通过当前边能够找到更短的路径，则更新 minDist 数组，并将终点 to 节点加入队列。
- 如果某个节点进入队列的次数超过 n-1 次，则说明图中存在负权回路，设置 flag = true 并终止循环。
结果输出：
- 如果存在负权回路，输出 "circle"。
- 如果 minDist[end] 仍然是 Integer.MAX_VALUE，说明终点无法到达，输出 "unconnected"。
- 否则输出起点到终点的最短路径值。

时间复杂度和空间复杂度

时间复杂度：理论上最坏情况下，SPFA 的时间复杂度为 O(N * E)，其中 N 为节点数量，E 为边的数量。
空间复杂度：O(N)，主要用于存储 minDist 和 count 数组，以及队列的空间。

bellman_ford之单源有限最短路

文章讲解

思路

注意题目中描述是最多经过 k 个城市的条件下，而不是一定经过k个城市，也可以经过的城市数量比k小，但要最短的路径。
本题是最多经过 k 个城市，那么是 k + 1条边相连的节点。如图：

image.png
图中，节点1 最多已经经过2个节点到达节点4，中间是有3 条边。
所以本题就是求：起点最多经过k + 1 条边到达终点的最短距离。
对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离，那么对所有边松弛 k + 1次，就是求起点到达与起点k + 1条边相连的节点的最短距离。

代码实现

注意：每次计算 minDist 时候，要基于对所有边上一次松弛的 minDist 数值才行，所以我们要记录上一次松弛的minDist。
版本1（过不了）

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 节点数量
        int m = sc.nextInt(); // 边的数量

        List<int[]> grid = new ArrayList<>();

        // 读取所有边的信息
        for (int i = 0; i < m; i++) {
            int p1 = sc.nextInt();
            int p2 = sc.nextInt();
            int val = sc.nextInt();
            // p1 指向 p2，权值为 val
            grid.add(new int[]{p1, p2, val});
        }

        int src = sc.nextInt(); // 起点
        int dst = sc.nextInt(); // 终点
        int k = sc.nextInt();   // 松弛次数

        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[src] = 0;

        for (int i = 1; i <= k + 1; i++) { // 对所有边松弛 k + 1 次
            for (int[] side : grid) {
                int from = side[0];
                int to = side[1];
                int price = side[2];
                if (minDist[from] != Integer.MAX_VALUE && minDist[to] > minDist[from] + price) {
                    minDist[to] = minDist[from] + price;
                }
            }

            // 打印 minDist 数组
            for (int j = 1; j <= n; j++) {
                if (minDist[j] == Integer.MAX_VALUE) {
                    System.out.print("INF ");
                } else {
                    System.out.print(minDist[j] + " ");
                }
            }
            System.out.println();
        }

        if (minDist[dst] == Integer.MAX_VALUE) {
            System.out.println("unreachable"); // 不能到达终点
        } else {
            System.out.println(minDist[dst]); // 输出到达终点的最短路径
        }

        sc.close();
    }
}

版本2

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 节点数量
        int m = sc.nextInt(); // 边的数量

        List<int[]> grid = new ArrayList<>();

        // 读取所有边的信息
        for (int i = 0; i < m; i++) {
            int p1 = sc.nextInt();
            int p2 = sc.nextInt();
            int val = sc.nextInt();
            grid.add(new int[]{p1, p2, val});
        }

        int src = sc.nextInt(); // 起点
        int dst = sc.nextInt(); // 终点
        int k = sc.nextInt();   // 松弛次数

        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[src] = 0;

        int[] minDistCopy = new int[n + 1]; // 用来记录上一次遍历的结果

        for (int i = 1; i <= k + 1; i++) {
            System.arraycopy(minDist, 0, minDistCopy, 0, n + 1); // 复制上一次计算的结果

            for (int[] side : grid) {
                int from = side[0];
                int to = side[1];
                int price = side[2];
                // 使用 minDistCopy 来计算 minDist 
                if (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + price) {
                    minDist[to] = minDistCopy[from] + price;
                }
            }
        }

        if (minDist[dst] == Integer.MAX_VALUE) {
            System.out.println("unreachable"); // 不能到达终点
        } else {
            System.out.println(minDist[dst]); // 输出到达终点的最短路径
        }

        sc.close();
    }
}

拓展2：本题本质

本题的两个因素：
- 本题可以有负权回路，说明只要多做松弛，结果是会变的。
- 本题要求最多经过k个节点，对松弛次数是有限制的。
所以本题为什么计算minDist 一定要基于上次的 minDist 数值

拓展3：SPFA

拓展4：能否用dijkstra

看不动了，二刷再来

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,056评论 5赞 474
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,842评论 2赞 378
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 148,938评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,296评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,292评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,413评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,824评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,493评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,686评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,502评论 2赞 318
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,553评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,281评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,820评论 3赞 305
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,873评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,109评论 1赞 258
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,699评论 2赞 348
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,257评论 2赞 341

代码随想录算法训练营第61天 | 图论part10：Bellman_ford 队列优化算法、bellman_ford之判断负权回路、bellman_ford之单源有限最短路

第十一章：图论part10

Bellman_ford 队列优化算法（又名SPFA）

思路

1. 模拟过程

2. Java 代码实现

3. 模拟过程举例

4. 效率分析

5. 拓展

bellman_ford之判断负权回路

思路

代码实现

代码解释

时间复杂度和空间复杂度

拓展： 使用 队列优化版的bellman_ford

代码实现

代码解析

时间复杂度和空间复杂度

bellman_ford之单源有限最短路

思路

代码实现

拓展2：本题本质

拓展3：SPFA

拓展4：能否用dijkstra

推荐阅读更多精彩内容

拓展：使用队列优化版的bellman_ford