- 算法导入
- 算法核心
- 代码实现
- 参考资料
- 结尾
在图论中，求最短路径有一个经典的算法 Dijkstra算法（银行家算法其实也是这人提出的），就离谱。
如果已经忘了，出门右拐——银行家算法
Dijkstra（/ˈdikstrɑ/或/ˈdɛikstrɑ/）算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表，是一种求解 非负权图 上单源最短路径的算法。
上面一段话有两点需要注意：1. 非负权图。指所有路径的权值都非负。2. 单源。指从一个源点到其他点的最短路径。
那有人想问了，求每对结点之间的最短路径，用啥呢？Floyd算法、Johnson算法。
那对于负权图，上面的算法能用吗？能用，你还能用 Bellman-Ford算法。
那，我说停停。
好，言归正传。咱们这节先介绍 Dijkstra算法，为后面的几种算法铺个路。正式开始前先告知一些图论中的定义：
- n ，图上点的数目， m 图上边的数目。
- s： 为最短路的源点。
- dis(u) ：源点 s 到 u 点的最短路长度。
- w(u,v) ：边(u, v) 的权值。
Dijkstra算法的思想为 贪心，每次选择最短路长度最小的点，来更新相连边的最短路。从局部最优到全局最优。
初始化：
将结点分为两个集合：已确定最短路点集合 S 和 待确定最短路点集合 T。初始时，所有点都在 T 中。
初始化 dis(s) = 0，其余点的 dis 均为 正无穷。
重复操作：
- 从T集合中，选取一个最短路长度最小的结点，移到S集合中。
- 对刚加入S集合的所有出边，执行松弛操作。
直到T集合为空，算法结束。可能有读者不理解松弛操作是啥，公式解答如下：
对于边 (u,v) 松弛操作为： dis(v) = min(dis(v) , dis(u) + w(u,v) )
你在的城市只能坐绿皮火车去北京，哎呀老远了，要1天才能到达。突然你发现去省会只要2小时，省会坐飞机去北京只要5小时，合计7个小时，这不更香了？那肯定赶紧更新这个最短路径。
建议大家去这 oi-wiki，查看详细的正确性证明 + 时间复杂度分析。咱的重点放在如何实现。
代码实现由于图不同的存储方式，复杂度也不同，这里只提供较为普遍使用的两种存图方式。
针对稀疏图 m ≈ n，邻接表存图，优先队列维护最短路长度最小的结点。
import java.util.*;
public class Solution {
List[] graph;
int[] dis;
boolean[] vis;
public static final int INF = Integer.MAX_VALUE / 2;
public void dijkstra(int n, int[][] edge, int s) {
// 1. 抽象化。根据edge信息建图。
// 注意：有时候edge并不会直接给出，比如一些题目给出的是字符串表示的结点，那么需要使用 Map 来 给字符串编号，再抽象化
graph = new List[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] e : edge) {
// w(e[0], e[1]) = e[2]
graph[e[0]].add(new int[]{e[1], e[2]});
}
// 2. 初始化源点到其他点的最短距离
dis = new int[n];
Arrays.fill(dis, INF);
// 源点到自身的距离为0
dis[s] = 0;
// 3. 初始化访问标志，默认为false
vis = new boolean[n];
// 4. 初始化优先队列, 根据权值升序排序
PriorityQueue pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.add(new int[]{s, 0});
// 5. dijkstra
while (!pq.isEmpty()) {
// 弹出最短路长度最小的点 和 其权值
int[] temp = pq.poll();
int u = temp[0];
// 访问过，跳过
if (vis[u]) {
continue;
}
vis[u] = true;
// 遍历所有 u 能够到达的点，刚开始为 u = s
for (int[] q: graph[u]) {
// 下一个点 v, 即其边权值 w
int v = q[0], w = q[1];
if (dis[v] > dis[u] + w) {
// s->v 的距离 > s->u 的距离 + u->v 的距离，更新最短距离，注意时 s-> 其他点 距离为 +∞
dis[v] = dis[u] + w;
// 加入优先队列，s->v 的距离 dis[v]
pq.add(new int[]{v, dis[v]});
}
}
}
}
}
针对稠密图m ≈ n^2，采用邻接矩阵存储
import java.util.*;
public class Solution2 {
int[][] graph;
boolean[] vis;
int[] dis;
int INF = Integer.MAX_VALUE / 2;
public void dijkstra(int n, int s, int[][] edges) {
// 1. 初始化邻接矩阵
graph = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(graph[i], INF);
// 点到自身的权值为0
graph[i][i] = 0;
}
for (int[] e : edges) {
graph[e[0]][e[1]] = e[2];
}
// 2. 初始化源点到其他点的距离
dis = new int[n];
Arrays.fill(dis, INF);
// 源点到自身的距离为0
dis[s] = 0;
// 3. 初始化访问标志
vis = new boolean[n];
// 4. 迭代n次
for (int i = 0; i < n; i++) {
// 每次找到[最短距离最小] 且 [没有更新] 点 t
int u = 0, min = INF;
for (int j = 0; j < n; j++) {
if (!vis[j] && dis[j] < min) {
u = j;
min = dis[j];
}
}
vis[u] = true;
// 用点u的[最小距离]更新其他点
for (int j = 0; j < n; j++) {
if (dis[u] + graph[u][j] < dis[j]) {
dis[j] = dis[u] + graph[u][j];
}
}
}
}
}
参考资料
OI Wiki
图灵程序设计丛书 算法 第4版
如果有天兜兜转转再一次相遇 我一定会不顾一切紧紧抱着你
许嵩 《庞贝》
