Dijkstra算法

概念

Dijkstra 算法是一个可以解决单一源点最短路径问题的经典算法，本质上是对广度优先搜索（BFS）的一个推广，只是把 BFS 维护的栈换成了优先队列。

Dijkstra算法成立的前提条件是不存在负权的边，这意味任何一条路径，从起点开始到路径中每个点的距离都是依次递增的。所以按照递增的顺序来依次计算出最短路径也就是Dijkstra算法了

每次循环都会增多一个保证已经找到最短路的点。

直观来说，如果我们已经求出了k个离源点距离最近的点，以及它们各自的距离，那么到源点距离第k+1近的点，它到源点的最短路径只能经过这前k个点——如果经过了其他点，那么这个其他点显然离源点更近，那这个点一定不是第k+1近了。既然只经过这前k个点，那么只用这前k个点放缩就可以找到那个最短路径了。再加上前k-1个点上一轮已经放缩过，所以每一轮只需要用新加入的节点进行放缩就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int g[][] = new int[n][n];
for (int i = 0; i < n; i++) Arrays.fill(g[i], -1);
for (int[] time : times) {
   int cur = time[0] - 1, next = time[1] - 1, len = time[2];
   g[cur][next] = len;
}
int dis[] = new int[n];
Arrays.fill(dis, Integer.MAX_VALUE);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
dis[k - 1] = 0;
pq.offer(new int[]{k-1, 0});
while (!pq.isEmpty()) {
   int poll[] = pq.poll(), cur = poll[0], d = poll[1];
   for (int i = 0; i < n; i++) {
         if (g[cur][i] == -1) continue;
         if (d + g[cur][i] < dis[i]) {
            dis[i] = d + g[cur][i];
            pq.offer(new int[]{i, dis[i]});
         }
   }
}
int res = Arrays.stream(dis).max().getAsInt();
return res == Integer.MAX_VALUE ? -1 : res;

无法处理有负边的图

举例：

第一次贪心得到的点的路径s->v不是最短路

拓展

  1. 判断图中某一个点是否在最短路径中
    1. 回溯：计算最短路径过程中同时记录每个点的父节点们，最后得到最短路径后，从终点开始回溯
    2. 双边dijkstra：计算起点s到终点e和终点到起点的dijkstra最短路径dis[]和dis2[]，判断起点到这个点的最短路径 + 这个点到终点的最短路径 是否等于起点到终点的最短路径，即dis[v] + dis2[v] == dis[e]
  2. 判断图中某一个边是否在最短路径中
    1. 回溯：同理
    2. 双边dijkstra：对于边(u,v,w)，判断dis[x] + dis2[y] + w == dis[n-1] || dis[y] + dis2[x] + w == dis[n-1]

相关证明

题解