代码随想录Day74(图论Part10)

94. 城市间货物运输| (Bellman_ford队列优化版 / SPFA)

题目:94. 城市间货物运输 I (kamacoder.com)

思路:

Bellman_ford 算法 每次都是对所有边进行松弛,其实是多做了一些无用功。

只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了

因此,关键在于记录上次松弛更新过的节点,用队列来记录。

答案
import java.util.*;

class Edge {
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w) {
        to = t;
        val = w;
    }
}

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

        int n = scanner.nextInt();  // 顶点数
        int m = scanner.nextInt();  // 边数

        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 将所有边保存起来
        for (int i = 0; i < m; i++) {
            int p1 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            // p1 指向 p2,权值为 val
            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); // 队列里放入起点

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (Edge edge : graph.get(node)) {
                int from = node;
                int to = edge.to;
                int value = edge.val;
                if (minDist[to] > minDist[from] + value) { // 开始松弛
                    minDist[to] = minDist[from] + value;
                    queue.offer(to);
                }
            }
        }

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

        scanner.close();
    }
}
小结

邻接表存储,方便找到 上一次松弛时,更新过的节点作为出发节点所连接的边

List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
    graph.add(new ArrayList<>());
}

 使用LinkedList实现Queue,不断从中 poll 出节点node,操作 node 的 edge,将 node.to 加入到队列中

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

while (!queue.isEmpty()) {
    int node = queue.poll();

    for (Edge edge : graph.get(node)) {
        int from = node;
        int to = edge.to;
        int value = edge.val;
        if (minDist[to] > minDist[from] + value) { // 开始松弛
            minDist[to] = minDist[from] + value;
            queue.offer(to);
        }
    }
}

95.城市间货物运输|| (Bellman_ford判断负权回路)

题目:95. 城市间货物运输 II (kamacoder.com)

思路:出现负权回路,按照之前的思路,会一直循环回路,使得成本不断减小,因此核心思路是,在Bellman_ford标准版基础上,再松弛一次,看结果是否变化

SPFA(Bellman_ford优化版),则是看节点加入队列次数是否超过n-1次

答案
import java.util.*;

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

        int n = scanner.nextInt();  // 顶点数
        int m = scanner.nextInt();  // 边数

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

        // 将所有边保存起来
        for (int i = 0; i < m; i++) {
            int p1 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            edges.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[] edge : edges) {
                int from = edge[0];
                int to = edge[1];
                int price = edge[2];
                if (i < n) {
                    if (minDist[from] != Integer.MAX_VALUE && minDist[to] > minDist[from] + price) {
                        minDist[to] = minDist[from] + price;
                    }
                } else { // 多加一次松弛判断负权回路
                    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]);
        }

        scanner.close();
    }
}

95.城市间货物运输|||(Bellman_ford单源有限最短路径)

题目:96. 城市间货物运输 III (kamacoder.com)

思路:关键是在于,每次松弛要基于上一次松弛的结果

答案
import java.util.*;

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

        int n = scanner.nextInt();  // 顶点数
        int m = scanner.nextInt();  // 边数

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

        // 将所有边保存起来
        for (int i = 0; i < m; i++) {
            int p1 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            edges.add(new int[]{p1, p2, val});
        }

        int src = scanner.nextInt();  // 起点
        int dst = scanner.nextInt();  // 终点
        int k = scanner.nextInt();    // 最大边数

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

        int[] minDistCopy = new int[n + 1];

        // 进行 k+1 次松弛操作
        for (int i = 1; i <= k + 1; i++) {
            System.arraycopy(minDist, 0, minDistCopy, 0, minDist.length); // 获取上一次计算的结果
            for (int[] edge : edges) {
                int from = edge[0];
                int to = edge[1];
                int price = edge[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]); // 到达终点最短路径
        }

        scanner.close();
    }
}
小结

更新用的是minDist,判断用的是minDistCopy

if (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + price) {
    minDist[to] = minDistCopy[from] + price;
}

相关推荐

  1. 代码随想Day74Part10

    2024-07-09 17:26:05       11 阅读
  2. 代码随想Day76Part11

    2024-07-09 17:26:05       5 阅读
  3. 代码随想Day72Part08)

    2024-07-09 17:26:05       11 阅读
  4. 代码随想-

    2024-07-09 17:26:05       17 阅读
  5. 代码随想学习 54day from代码随想

    2024-07-09 17:26:05       2 阅读

最近更新

  1. 防范缓冲区溢出攻击的方法

    2024-07-09 17:26:05       0 阅读
  2. 【如何使用Python编程】

    2024-07-09 17:26:05       0 阅读
  3. 【Python中的列表是什么】

    2024-07-09 17:26:05       0 阅读
  4. 数学建模--灰色关联分析法

    2024-07-09 17:26:05       0 阅读
  5. 什么是 MLPerf?

    2024-07-09 17:26:05       0 阅读

热门阅读

  1. 如何使一个盒子水平垂直居中(常用的)

    2024-07-09 17:26:05       5 阅读
  2. mybatis用注解替换xml,不再写.xml了

    2024-07-09 17:26:05       8 阅读
  3. Docker

    Docker

    2024-07-09 17:26:05      7 阅读
  4. 服务器安装多个Tomcat

    2024-07-09 17:26:05       7 阅读
  5. 玩转springboot之springboot定制化tomcat

    2024-07-09 17:26:05       9 阅读
  6. Word使用中的一些烦人的小问题

    2024-07-09 17:26:05       7 阅读
  7. Redis 中的跳跃表是什么

    2024-07-09 17:26:05       9 阅读
  8. 大语言模型系列-Transformer介绍

    2024-07-09 17:26:05       6 阅读