Dijkstra求最短路 I

Java解题思路：

• 1、邻接表的方式，使用链式前向星建立图
• 2、注意初始化dist数组为INF，h表头数组为-1因为在for循环遍历的时候-1表示结束循环
• 3、算法思路，计算i->j的距离，更新的时候是i->t,t->j的方式

import java.util.*;

public class Main {
    private static int N = 510;
    private static int M = 100010; // m边
    private static int[] e = new int[M];
    private static int[] ne = new int[M];
    private static int[] h = new int[N]; // 顶点n
    private static int[] w = new int[M]; // 权重
    private static int idx = 0;
    private static int[] dist = new int[N]; // dist[x] = y表示起点到x的最小距离是y
    private static boolean[] st = new boolean[N]; // 表示顶点被访问

    private static void add(int a, int b, int c) { // 建图
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h, -1);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            add(x, y, z);
        }
        int res = dijkstra(n);
        System.out.println(res);
        sc.close();
    }

    private static int INF = 0x3f3f3f3f;
    private static int dijkstra(int n) { // 参数传入节点n
        Arrays.fill(dist, INF); // 初始化距离数据访问距离都是INF
        dist[1] = 0; // 起点1到1的距离是0
        for (int p = 0; p < n; p++) {
            int t = -1;
            for (int j = 0; j < n; j++) { // 遍历dist数组，找到没有确定最短路径的节点中最近的节点
                if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            st[t] = true; // 标记t被访问
            for (int j = h[t]; j != -1; j = ne[j]) { // 访问t节点的邻接表
                int i = e[j];
                dist[i] = Math.min(dist[i], dist[t] + w[j]); // 更新i - j的距离，i-j转化为i-t，t-j的距离
            }
        }
        if (dist[n] == INF) {
            return -1;
        }
        return dist[n];
    }

}