Acwing 849. Dijkstra求最短路 I

题目

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n号点，则输出 ?1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n号点的最短距离。

如果路径不存在，则输出 ?1。

数据范围

1≤n≤500
1≤m≤105
图中涉及边长均不超过10000。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

代码与解析

模板题啦，一定要掌握的

以上这张图是最短路算法问题的解法算法

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, m, N = 10010;
    static int[] dis = new int[510];
    static int[][] g = new int[510][510];
    static boolean[] state = new boolean[510];  // 记录节点状态，true表示已确定最短路径

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

        // 初始化邻接矩阵，初始值为 N 表示无穷大
        for (int i = 1; i <= n; i++) {
            Arrays.fill(g[i], N);
        }

        // 输入图的边信息，记录最小的边权值
        for (int i = 0; i < m; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            int z = in.nextInt();
            g[x][y] = Math.min(g[x][y], z);
        }

        System.out.println(dijkstra());
    }

    public static int dijkstra() {
        Arrays.fill(dis, N); // 初始化距离数组，初始值为 N 表示无穷大
        dis[1] = 0; // 起点到自身距离为0

        // 循环进行n次，每次找到一个离起点最近的节点，更新其相邻节点的距离
        for (int i = 1; i < n; i++) {
            int t = -1; // t 存储当前访问的节点

            // 找到未确定最短路径的节点中距离起点最近的节点
            for (int j = 1; j <= n; j++) {
                if (!state[j] && (t == -1 || dis[t] > dis[j])) {
                    t = j;
                }
            }

            state[t] = true; // 将该节点标记为已确定最短路径

            // 更新相邻节点的距离
            for (int j = 1; j <= n; j++) {
                dis[j] = Math.min(dis[j], dis[t] + g[t][j]);
            }
        }

        return dis[n] == N ? -1 : dis[n]; // 如果终点距离为无穷大，说明不可达，返回-1，否则返回最短距离
    }
}

1. 输入： 从输入中获取节点数 n、边数 m 以及图的边信息。

2. 初始化： 初始化邻接矩阵 g 和距离数组 dis，将所有距离初始值设置为无穷大 N，状态数组 state 用于记录节点的最短路径是否已确定。

3. 构建图： 遍历输入的边信息，记录每条边的最小权值。

4. Dijkstra 算法： 使用 Dijkstra 算法求解最短路径。

   • 从起点开始，每次选择未确定最短路径的节点中距离起点最近的节点，标记该节点为已确定最短路径。
   • 更新该节点的相邻节点的距离，取最小值。
   • 重复以上步骤，直到所有节点的最短路径都被确定。

5. 输出结果： 输出终点到起点的最短距离，若不可达则输出 -1