【算法】图的最短路径-Dijkstra算法（Java）
图的最短路径常用算法有 Dijkstra 算法，Bellman-Ford 算法，SPFA 算和 Floyd 算法。今天先学习 Dijkstra 算法。
1.Dijkstra 算法
迪杰斯特拉算法，用来解决单元最短路问题，用于求 s 到其他所有顶点的最小路径。基本思想是，对于图 G(V, E)，V 是顶点，E 是边。设置集合 S 存放已经访问过的节点。每次从 V 减去 S（也就是没访问的节点）中选择与起点 s 距离最短的点 u，加入集合 S。以 u 为中介点，优化起点 s 与所有从 u 能到达的顶点 v 之间的最短路径。执行 n 次知道所有顶点都被访问。下面给出邻接表存储图的 Dijkstra 算法的代码
private List<List<Integer>> edges; // 邻接表,存放能到达的点
private List<List<Integer>> weights; // 邻接表,存放能到达的点的边权
private int n; // 顶点数
private int[] dis; // 起点到达各点的最短路径长度
private boolean[] visited; // 标记是否访问过
private final int INF = Integer.MAX_VALUE / 2; // 定义一个最大值，因为有加法运算，除以 2 防止溢出
public void Dijkstra(int s) { // s 为起点
dis = new int[n];
Arrays.fill(dis, INF); // 设置所有点不可达
dis[s] = 0; // 起点到达自身距离为 0
for (int i = 0; i < n; i++) {
int u = -1; // 在未访问过的顶点中寻找 dis 最小的顶点 u
int min = INF; // 最小的 dis 存放在 min 中
for (int j = 0; j < n; j++) {
if (visited[j] == false && dis[j] < min) { // 有距离更小的点，那么更新顶点 u 和 最小距离 min
u = j;
min = dis[j];
}
}
if (u == -1) return; // 不可达，直接返回
visited[u] = true;
List<Integer> edge = edges.get(u); // 取出 u 能到达的点
List<Integer> weight = weights.get(u); // 取出 u 能到达的点的权值
for (int j = 0; j < edge.size(); j++) {
int v = edge.get(j);
// 如果以 u 作为中介，能使到达 v 的 dis 变小，那么就更新 dis[v]
if (visited[v] == false && dis[u] + weight.get(j) < dis[v]) {
dis[v] = dis[u] + weight.get(j); // 优化 dis[v]
}
}
}
}
2.练习：力扣743. 网络延迟时间
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向边的传递时间。times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2
输出：-1
直接套用 模板即可：
class Solution {
private List<List<Integer>> edges = new ArrayList<>(); // 邻接表,存放能到达的点
private List<List<Integer>> weights = new ArrayList<>(); // 邻接表,存放能到达的点的边权
private int N; // 顶点数
private int[] dis; // 起点到达各点的最短路径长度
private boolean[] visited; // 标记是否访问过
private final int INF = Integer.MAX_VALUE / 2;
public int networkDelayTime(int[][] times, int n, int k) {
N = n + 1;
edges = new ArrayList<>();
weights = new ArrayList<>();
dis = new int[N];
visited = new boolean[N];
for (int i = 0; i < N; i++) {
edges.add(new ArrayList<>());
weights.add(new ArrayList<>());
}
for (int[] time : times) {
edges.get(time[0]).add(time[1]);
weights.get(time[0]).add(time[2]);
}
Dijkstra(k);
int result = 0;
for (int i = 1; i <= n; i++) result = Math.max(result, dis[i]);
return result == INF ? -1 : result;
}
public void Dijkstra(int s) { // s 为起点
Arrays.fill(dis, INF);
dis[s] = 0; // 起点到达自身距离为 0
for (int i = 1; i < N; i++) {
int u = -1; // 在未访问过的顶点中寻找 dis 最小的顶点 u
int min = INF; // 最小的 dis 存放在 min 中
for (int j = 1; j < N; j++) {
if (visited[j] == false && dis[j] < min) {
u = j;
min = dis[j];
}
}
if (u == -1) return;
visited[u] = true;
List<Integer> edge = edges.get(u);
List<Integer> weight = weights.get(u);
for (int j = 0; j < edge.size(); j++) {
int v = edge.get(j);
if (visited[v] == false && dis[u] + weight.get(j) < dis[v]) {
dis[v] = dis[u] + weight.get(j); // 优化 dis[v]
}
}
}
}
}
Reference
[1]力扣743. 网络延迟时间：https://leetcode-cn.com/problems/network-delay-time