6-BellmanFord算法

算法思想

松弛操作

松弛操作是一个用于不断更新最短路径估计值的操作

算法模板

import java.util.*;
public class Main {
    static int N = 510, M = 10010,
	    // INF 代表正无穷
		INF = 0x3f3f3f3f;
    static int n, m, k;
    static int[] dist = new int[N];
    // edges[]存储每条边的起点、终点和权重
    static Edge[] edges = new Edge[M];
        
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        Arrays.fill(dist, INF);
        
        for(int i = 0; i < m; i ++ )
        {
            int from = in.nextInt(), to = in.nextInt();
            int weight = in.nextInt();
            
            edges[i] = new Edge(from, to, weight);
        }
        
        bellman_fold();
        // 为什么判定条件是 dist[n] > INF / 2，而不是 dist[n] == INF
        // 因为当第一个节点无法达到第 n 个节点，dist[n]的值可能被更新
        if(dist[n] > INF / 2) System.out.println("impossible");
        else System.out.println(dist[n]);
    }
    
    public static void bellman_fold()
    {
		// 有向图的最短路径数组的状态 随着经过的边的数量发生变化
	    // 经过0条边后，最短路径数组的状态
        dist[1] = 0;
	    // 经过 i 条边后，最短路径数组的状态
        for(int i = 1; i <= k; i ++)
        {
            // 以上一个状态为起点，开始执行松弛操作
            // 遍历所有边，执行松弛操作
            int[] last = dist.clone();
            for(int j = 0; j < m; j ++ )
            {
                Edge e = edges[j];
                dist[e.to] = Math.min(dist[e.to], last[e.from] + e.weight);
            }
        }
        
    }
}

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