Day59--图论--47. 参加科学大会（卡码网），94. 城市间货物运输 I（卡码网）

Day59–图论–47. 参加科学大会（卡码网），94. 城市间货物运输 I（卡码网）

今天学习了dijkstra（堆优化版），比较一下它和昨天的dijkstra（朴素版）优化在了哪里？为什么dijkstra不能计算有负值权重的最短路径？要使用Bellman_ford，它像不像动态规划？

47. 参加科学大会（卡码网）

方法：dijkstra（堆优化版）

思路：

就像Prim和Kruskal一样，一个是针对点，一个是针对边。dijkstra朴素版针对于点，而堆优化版针对于边——所以适用于稀疏图。

1. 传统三步曲：
   1. 第一步，选源点到哪个节点近且该节点未被访问过
   2. 第二步，该最近节点被标记访问过
   3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
2. 改用邻接表存储（定义一个Edge类，每个edge存储指向的节点to和边的权重val。每个节点都拥有一个LinkedList<Edge>来存储自己的邻接表）
3. 使用int[] minDist数组，存储从源点到每个节点的最短距离。
4. 新定义一个Pair类，存储两个值，一个是节点，一个是从源点到每个节点的最短距离。其实存的东西和minDist是一样的，本意就如此，用途不同：更新完非访问节点到源点的距离的时候，一边更新minDist，一边组成一个Pair，丢到小顶堆PriorityQueue里面去。
5. 堆优化三步曲：
   1. 第一步，从小顶堆PriorityQueue取一个源点到目前点距离最小的节点。
   2. 第二步，该最近节点被标记访问过
   3. 第三步，更新非访问节点到源点的距离（即，取该节点的邻接表，对于未访问的邻接元素，更新minDist，并组装一个Pair丢到小顶堆里）

import java.util.*;

// 小顶堆的比较器
class HeapComparison implements Comparator<Pair> {

    @Override
    public int compare(Pair p1, Pair p2) {
        return Integer.compare(p1.weight, p2.weight);
    }
}

// 定义一个类来表示键值对
class Pair {
    int node; // 节点
    int weight; // 源点到该节点的权值

    Pair(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }
}

// 定义一个类来表示带权重的边
class Edge {
    int to; // 邻接顶点
    int val; // 边的权重

    Edge(int to, int val) { // 构造函数
        this.to = to;
        this.val = val;
    }
}

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

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

        for (int i = 0; i < m; i++) {
            int p1 = in.nextInt();
            int p2 = in.nextInt();
            int val = in.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);

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

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

        // 初始化队列，源点到源点的距离为0
        pq.add(new Pair(start, 0));
        minDist[start] = 0; // 起始点到自身的距离为0

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

            if (visited[cur]) continue;

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

            // 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
            for (Edge edge : grid.get(cur)) { // 遍历 cur指向的节点
                // cur指向的节点edge.to，这条边的权值为 edge.val
                if (!visited[edge.to]
                        && minDist[cur] != Integer.MAX_VALUE
                        && minDist[cur] + edge.val < minDist[edge.to]) { // 更新minDist
                    minDist[edge.to] = minDist[cur] + 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]); // 到达终点最短路径
        }
    }
}

94. 城市间货物运输 I（卡码网）

Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。

其实 Bellman_ford算法 也是采用了动态规划的思想，即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。

Bellman_ford 是可以计算 负权值的单源最短路算法。

其算法核心思路是对 所有边进行 n-1 次 松弛。

方法：Bellman_ford

思路：

其实松弛操作，就是进行“动态规划”。因为每更新一个节点的状态，都会影响其它节点。

所以每更新一个节点，就需要对全部节点的状态进行更新。（n个节点，更新n-1一次就够了）

核心代码：minDist[B] = min(minDist[A] + value, minDist[B])

也就是说，如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 minDist[B] > minDist[A] + value，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。

import java.util.*;

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 class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        List<Edge> edges = new ArrayList<>();

        // 将所有边保存起来
        for (int i = 0; i < m; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            int val = in.nextInt();
            edges.add(new Edge(from, to, val));
        }
        int start = 1; // 起点
        int end = n; // 终点

        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[start] = 0;
        // 对所有边 松弛 n-1 次（这里遍历的是节点，从1遍历到n-1）
        for (int i = 1; i < n; i++) {
            // 每一次松弛，都是对所有边进行松弛
            for (Edge e : edges) {
                // 松弛操作
                // minDist[from] != Integer.MAX_VALUE 防止从未计算过的节点出发
                if (minDist[e.from] != Integer.MAX_VALUE) {
                    // 动态规划，更新e.to这个节点的minDist
                    minDist[e.to] = Math.min(minDist[e.to], minDist[e.from] + e.val);
                }
            }
        }
        // 不能到达终点
        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.println("unconnected");
        } else {
            // 到达终点最短路径（运输成本最小）
            System.out.println(minDist[end]);
        }
    }
}