AcWing 849. Dijkstra求最短路 I -- JAVA + 详细注解
原题链接
简单
作者:
卑微的人423
,
2023-03-22 21:15:24
,
所有人可见
,
阅读 220
JAVA 代码 + 注解
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int n;
public static int m;
public static int[][] map; // 邻接矩阵
public static int[] dis; // 源点到每个点的最短路径,默认为正无穷,即还没有计算到此点的最短路径
public static boolean[] vis; // 每个点是否遍历过
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
map = new int[n + 1][n + 1];
dis = new int[n + 1];
vis = new boolean[n + 1];
for(int[] m : map) {
Arrays.fill(m, Integer.MAX_VALUE);
}
for (int i = 1; i <= m; i++) {
int u = scan.nextInt(); // 起点
int v = scan.nextInt(); // 终点
int w = scan.nextInt(); // 权值
map[u][v] = Math.min(w, map[u][v]); // 防止重边的影响,存小的那个
}
dijsktra();
scan.close();
}
public static void dijsktra() {
Arrays.fill(dis, Integer.MAX_VALUE);
dis[1] = 0; // 默认源点是编号为1的点,此点的到此点的最短路径为0
for (int i = 0; i < n; i++) { // 有n个点所以要遍历n次,最终会计算出每个点的最短路径
// 每次选择距离源点最近的点
int index = -1; // 距离最近的点的下标,默认为-1,即未找到,也用于判断最后是否找到了符合要求的点
int minDis = Integer.MAX_VALUE; // 距离源点最近的点到源点的距离
for (int j = 1; j <= n; j++) { // 遍历这n个点
if (!vis[j] && dis[j] < minDis) { // 未遍历过,且最短路径小于当前最短路径值,更新
minDis = dis[j];
index = j;
}
}
if (index == -1) { // 没找到符合要求的点
System.out.print("-1");
return;
}
vis[index] = true; // 找到则遍历此点
for (int j = 1; j <= n; j++) { // 去更新此点所能到达的点的最短路径
if (!vis[j] && map[index][j] != Integer.MAX_VALUE) { // 两点之间有边,且边的终点未被遍历过
dis[j] = Math.min(dis[j], dis[index] + map[index][j]); // 更新最短路径
}
}
}
System.out.print(dis[n]); // 输出源点到n(终点)的最短路径
}
}