代码随想录第五十九天| dijkstra（堆优化版）精讲 Bellman

本文链接：https://blog.csdn.net/Sweeping_Robot/article/details/146497354

Dijkstra算法（堆优化版）精讲

题目描述

小明需要从第一个车站出发，到达最后一个车站参加科学大会。途中各车站之间的道路状况、交通拥堵程度等因素会影响通行时间。小明希望选择一条时间最短的路线。

输入包含车站数量N和公路数量M，接下来M行每行三个整数S、E、V，表示从S车站到E车站的单向道路，花费V单位时间。输出从起点到终点的最短时间，若无法到达则输出-1。

输入输出示例

输入：

输出：

解题思路

算法原理

Dijkstra算法用于求解单源最短路径问题，适用于有权重的有向或无向图，且所有边的权重非负。堆优化版Dijkstra算法通过优先队列（小顶堆）来优化节点选择过程，降低时间复杂度。

图的存储

使用邻接表存储图结构，邻接表由数组和链表组成，每个节点对应一个链表，链表中存储该节点直接指向的其他节点及边的权重。

堆优化细节

优先队列：用优先队列（小顶堆）存储待处理的节点，按源点到该节点的当前最短距离排序，每次取出距离最小的节点进行处理。
节点选择：通过堆顶元素直接获取距离源点最近的未访问节点，避免遍历所有节点查找最小距离。
距离更新：处理当前节点时，遍历其邻接节点，若通过当前节点到达邻接节点的距离更短，则更新距离并将其加入优先队列。

代码实现

import java.util.*;

class Edge {
    int to;  // 邻接顶点
    int val; // 边的权重

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

class MyComparison implements Comparator<Pair<Integer, Integer>> {
    @Override
    public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs) {
        return Integer.compare(lhs.second, rhs.second);
    }
}

class Pair<U, V> {
    public final U first;
    public final V second;

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}

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>> 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 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            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);

        // 记录顶点是否被访问过
        boolean[] visited = new boolean[n + 1];

        // 优先队列中存放 Pair<节点，源点到该节点的权值>
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new MyComparison());

        // 初始化队列，源点到源点的距离为0，所以初始为0
        pq.add(new Pair<>(start, 0));

        minDist[start] = 0;  // 起始点到自身的距离为0

        while (!pq.isEmpty()) {
            // 1. 第一步，选源点到哪个节点近且该节点未被访问过（通过优先级队列来实现）
            // <节点， 源点到该节点的距离>
            Pair<Integer, Integer> cur = pq.poll();

            if (visited[cur.first]) continue;

            // 2. 第二步，该最近节点被标记访问过
            visited[cur.first] = true;

            // 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
            for (Edge edge : grid.get(cur.first)) { // 遍历 cur指向的节点，cur指向的节点为 edge
                // cur指向的节点edge.to，这条边的权值为 edge.val
                if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
                    minDist[edge.to] = minDist[cur.first] + edge.val;
                    pq.add(new Pair<>(edge.to, minDist[edge.to]));
                }
            }
        }

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

代码注释

Edge类：表示图中的边，包含目标节点编号和权重。
MyComparison类：用于优先队列的比较器，按距离大小排序。
Pair类：存储节点编号和对应的距离。
主函数：
- 读取输入，构建邻接表。
- 初始化距离数组和访问标记数组。
- 使用优先队列辅助Dijkstra算法，每次取出距离最小的节点，更新其邻接节点的距离。
- 最终输出终点的最短距离或-1。

总结

堆优化版Dijkstra算法通过优先队列优化节点选择过程，将时间复杂度从O(n^2)降低到O((n + m) log n)，适合处理稀疏图。理解邻接表的存储方式和优先队列的使用是掌握该算法的关键。

Bellman-Ford 算法精讲

题目描述

某国有 n 个城市，通过 m 条单向道路连接。每条道路有运输成本和政府补贴，权值为运输成本减去政府补贴。权值为正表示需支付费用，为负表示能盈利。要求找出从城市 1 到城市 n 的最低运输成本路径，若成本为负则表示盈利，若无路径则输出 “unconnected”。

输入包含 n 和 m，接着 m 行每行三个整数 s、t、v，表示从 s 到 t 的道路权值为 v。输出为最低成本或 “unconnected”。

输入输出示例

输入：

输出：

-4

解题思路

算法原理

Bellman-Ford 算法用于解决单源最短路径问题，尤其适用于图中存在负权边的情况。其核心思想是对所有边进行 n-1 次松弛操作，逐步更新源点到各节点的最短距离。

关键概念

松弛操作：对于一条边 (u, v) 权值为 w，若当前记录的源点到 v 的最短距离大于源点到 u 的最短距离加上 w，则更新源点到 v 的最短距离。这是 Bellman-Ford 算法的核心操作。
松弛次数：图中节点数为 n，最多经过 n-1 条边即可从源点到达任意其他节点，因此需要对所有边进行 n-1 次松弛操作。

代码实现

public class Main {

    // 定义边的类，包含起点、终点和权值
    static class Edge {
        int from;
        int to;
        int val;
        public Edge(int from, int to, int val) {
            this.from = from;
            this.to = to;
            this.val = val;
        }
    }

    public static void main(String[] args) {
        // 输入处理
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 城市数量
        int m = sc.nextInt(); // 道路数量
        List<Edge> edges = new ArrayList<>(); // 存储所有边

        // 读取每条道路的信息
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int val = sc.nextInt();
            edges.add(new Edge(from, to, val));
        }

        // 初始化最短距离数组
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE); // 初始时所有距离设为最大值
        minDist[1] = 0; // 源点到自身的距离为0

        // 进行n-1次松弛操作
        for (int i = 1; i < n; i++) {
            // 遍历所有边，尝试更新最短距离
            for (Edge edge : edges) {
                // 如果当前边的起点的最短距离不是最大值，并且可以通过这条边更新终点的最短距离
                if (minDist[edge.from] != Integer.MAX_VALUE && (minDist[edge.from] + edge.val) < minDist[edge.to]) {
                    minDist[edge.to] = minDist[edge.from] + edge.val; // 更新最短距离
                }
            }
        }

        // 输出结果
        if (minDist[n] == Integer.MAX_VALUE) {
            System.out.println("unconnected"); // 无法到达终点
        } else {
            System.out.println(minDist[n]); // 输出最短距离
        }
    }
}