Acwing 849. Dijkstra求最短路 I

发布时间:2024年01月16日

题目

给定一个 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

文章来源:https://blog.csdn.net/m0_51547272/article/details/135607728
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。