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

方法：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> {@Overridepublic 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，权值为 valgrid.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());// 初始化队列，源点到源点的距离为0pq.add(new Pair(start, 0));minDist[start] = 0; // 起始点到自身的距离为0while (!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.valif (!visited[edge.to]&& minDist[cur] != Integer.MAX_VALUE&& minDist[cur] + edge.val < minDist[edge.to]) { // 更新minDistminDist[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]); // 到达终点最短路径}}
}

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这个节点的minDistminDist[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]);}}
}