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

解题思想：

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

什么是松弛？

见上图中，想求minDist[B]，那么就要找到哪些状态可以推出minDist[B]。

状态一：minDist[C] + valueCB 可以推出 minDist[B]

状态二：minDist[B] 本身就是权值，可以推出自己

因此，重点在于如何从两个状态中选取得到真正的minDist[B]

举个例子，选取规则是取最小值，那么代码如下：

if(minDist[C] != Integer.MAX_VALUE && minDist[C] + valueCB < minDist[B]){
    minDist[B] = minDist[C] + valueCB;
}

这段代码就是 Bellman_ford 算法的核心。

这与动态规划求dp时的逻辑很相似，改写为dp算法常用递推公式

if(minDist[C] != Integer.MAX_VALUE){
    minDist[B] = min(minDist[C] + valueCB, minDist[B]);
}

为什么是对所有边进行n-1次松弛？

简单来讲，对所有边松弛一次，相当于计算 从源点出发只走一条边就可到达的节点 的最短距离；

对所有边松弛二次，相当于计算 从源点出发只走二条边就可到达的节点 的最短距离；

对所有边松弛三次，相当于计算 从源点出发只走三条边就可到达的节点 的最短距离；

以此类推，

对所有边松弛n-1次，相当于计算 从源点出发只走n-1条边就可到达的节点 的最短距离，那么此时就走完了所有的边，因为n个节点最多有n-1条边。

构建边Edge类，将边存入List集合。

扩展：如果松弛n次，松弛n+1次，松弛2*n次会发生什么？

答：结果是没有任何影响。因为本题说明：同时保证道路网格中不存在任何负权回路，即在有向图中不会出现有向环，且环的总权值为负数。

完整代码：

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<Edge> edges = new ArrayList<>(m);
        for(int i = 0; i < m; i++){
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            int v = scanner.nextInt();
            edges.add(new Edge(s, t, v));
        }
        //建立minDist数组
        int[] minDist = new int[n + 1];
        for(int i = 0; i < minDist.length; i++){
            minDist[i] = Integer.MAX_VALUE;
        }
        //源点是节点1，节点1到源点距离是0
        minDist[1] = 0;
        //Bellman_ford算法
        //开始遍历边,遍历n-1次
        for(int i = 0; i < n - 1; 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.print("unconnected");
        }else{
            System.out.print(minDist[n]);
        }    
    }    
}

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