1.Dijkstra算法（优先用堆优化实现方式）
主要步骤：
1.每次从未标记的节点中选择距离出发点最近的节点，标记，收录到最优路径集合中。
⒉计算刚加入节点A的邻近节点B的距离（不包含标记的节点)
若 （节点A的距离+节点A到节点B的边长)<节点B的距离 ，就更新节点B的距离和前面点。
本质是贪心算法：我现在就把出发点到B的已知的最短距离摆在这里，下次如果你要从出发点起出发路过B然后到达C，且B到C仅有一条路径，距离是固定的，因此必定是用先前求出来的出发点到B的最短距离来进行求解，这是出发点经过B到C的最短路径；当然，走到C可不止经过B这一种路径，还可能经过X到达C，那么我们这时候就可以维护出发点到达C的最短路，到时候这个到达C的最短路又可以用了；以此类推直至到达终点。
注意：Dijkstra算法只适用于权重为非负数的带权图！
或者和BFS进行类比，BFS是每次走1步，如果当路径很长时显然不现实；
因此，Dijkstra算法每次迭代是以节点作为单元，通常为了节省时间我们会用堆（TreeSet?） 来优化
总的时间复杂度为:O(NlogN) 空间复杂度:O(N) 其中N为边数
以上图为例，从节点0开始出发，从现在起只向前走，0已经被标记了不会再走回头路，marked=[0]；
节点[4,5] [6,7] [1,2] 入队，接下来先弹出距离起点最短的节点1([1,2])（为啥可以这么快弹出来？因为可以确定出发点0到节点1最短距离就是2，其他节点要想走到节点1只能从4和6走，又由于没有负边权其他路肯定更长，因此出发点到节点1的最短距离就是2）
节点弹出就意味着起点到弹出的节点最短距离已经确定了，此时可以标记掉节点1下次不用再走回头路，marked=[0,1]
节点1下面有节点2和3，此时计算后为[2,5] [3,5]入队；此时队列中元素为 que= [[4,5] [6,7] [2,5] [3,5]]
又进入下一轮的筛选，到起点距离最短的节点有3个，距离都为5
假如弹出节点4，那么[6,7]就会入队 此时队列为 que=[[6,7] [6,7] [2,5] [3,5]] marked=[0,1,4]
接下来弹出[2,5] 加入[5,6] 此时队列为 que=[[6,7] [6,7] [5,6] [3,5]] marked=[0,1,2,4]
弹出[3,5] 加入[5,6] 此时队列为 que=[[6,7] [6,7] [5,6] [5,6]] marked=[0,1,2,3,4]
弹出[5,6] 加入[6,7] 此时队列为 que=[[6,7] [6,7] [6,7] [5,6]] marked=[0,1,2,3,4,5]
弹出[5,6] 加入[6,7] 此时队列为 que=[[6,7] [6,7] [6,7] [6,7]] marked=[0,1,2,3,4,5]
弹出[6,7] 标记节点6 que=[[6,7] [6,7] [6,7]] marked=[0,1,2,3,4,5,6]
至此，搜索完毕，此时的节点0到节点6最短距离为7
关于 Dijkstra算法节点标记访问的问题：
1.如果是边权只有0与正数的，可以在入队时候直接标记，因为到时候兜回来肯定比现在的长（提高性能）；
2.如果边权不是上述情况，只能在弹出的时候标记访问，只有在弹出时才可以确定起点到该点的最短路径。
参考：
1.Dijkstra图解动画：【算法】最短路径查找—Dijkstra算法_哔哩哔哩_bilibili
2.三叶姐的最短路径模板(背下来)：三叶姐最短路模板
3.自己写的答案与例题：743. 网络延迟时间
4.矩阵型Dijkstra参考：
675. 为高尔夫比赛砍树
2290. 到达角落需要移除障碍物的最小数目
1368. 使网格图至少有一条有效路径的最小代价
Dijkstra标准模板(Q2290)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public int minimumObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] minCost = new int[m][n];
int INF = 0x3f3f3f3f;
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for (var arr : minCost) {
Arrays.fill(arr, INF);
}
minCost[0][0] = grid[0][0];
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.add(new int[]{minCost[0][0], 0, 0});
while (!pq.isEmpty()) {
int[] poll = pq.poll();
int x = poll[1], y = poll[2], cost = poll[0];
if (cost > minCost[x][y]) continue;
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int newCost = minCost[x][y] + grid[nx][ny];
if (newCost < minCost[nx][ny]) {
minCost[nx][ny] = newCost;
pq.add(new int[]{newCost, nx, ny});
}
}
}
}
return minCost[m - 1][n - 1];
}
}
|
vis数组标记写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public int minimumObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] minCost = new int[m][n];
int INF = 0x3f3f3f3f;
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
boolean[][] vis = new boolean[m][n];
for (var arr : minCost) {
Arrays.fill(arr, INF);
}
minCost[0][0] = grid[0][0];
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.add(new int[]{minCost[0][0], 0, 0});
vis[0][0] = true;
while (!pq.isEmpty()) {
int[] poll = pq.poll();
int x = poll[1], y = poll[2];
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny]) {
int newDis = minCost[x][y] + grid[nx][ny];
if (newDis < minCost[nx][ny]) {
minCost[nx][ny] = newDis;
vis[nx][ny] = true;
pq.add(new int[]{newDis, nx, ny});
}
}
}
}
return minCost[m - 1][n - 1];
}
}
|
注意自定义比较规则时候的一些细节：
1
2
3
4
5
| PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> cost[a[0]][a[1]));
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[O]));
|
2.01BFS
2290. 到达角落需要移除障碍物的最小数目
1368. 使网格图至少有一条有效路径的最小代价
我们都知道BFS是一种最基础的最短路径算法，因为队列保证了距离的二段性，先出队的距离必定小于等于后出队的距离，因此必定会以最短的路径找到终点，类似于洪水均匀蔓延的思想。
此算法是Dijkstra等求最短路的优秀替代
适用于求最短路径，但是有个要求：边权为0和1(或0和其他正数）。
求最短路的时间复杂度可以由 O(mlogn) 降到 O(m)！(n为点的个数，m为边的个数）
原理：这是 dijkstra 的优化，若边权只是 0 和 1 ，启用优先队列未免太浪费资源了！
用双端队列正是对这个地方的优化，将优先队列插入元素 O(logn) 的时间复杂度降到了 O(1)！！
过程：
从起点开始，加入队列。
while队列非空，取队首元素，用这个节点更新其他节点。
如果可以更新的话：
1、边权为0，放到队首。（从边权为0的边走，不增加消耗，得多走这样的边）
2、边权为其他，放到队尾。（增加消耗，少用）
（这样，队列前面的元素值一定比后面的元素值小（可以手动模拟下），每次求队首元素来更新相连的点的距离，完美的替代了优先队列的功能！）
因为将权重为0的节点加入进来不会使得当前最大距离变大，最短路径树还是处于同一层，相当于将等距线最大限度地蔓延到更远的地方。
参考：双端队列_01bfs——附详解典例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public int minimumObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int INF = 0x3f3f3f3f;
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int[][] dis = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(dis[i], INF);
}
dis[0][0] = 0;
Deque<int[]> que = new LinkedList<>();
que.add(new int[]{0, 0});
while (!que.isEmpty()) {
int[] p = que.poll();
int x = p[0], y = p[1];
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int nd = dis[x][y] + grid[nx][ny];
if (nd < dis[nx][ny]) {
dis[nx][ny] = nd;
if (grid[nx][ny] == 0) {
que.addFirst(new int[]{nx, ny});
} else {
que.addLast(new int[]{nx, ny});
}
}
}
}
}
return dis[m - 1][n - 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| public int minCost(int[][] grid) {
int m = grid.length, n = grid[0].length;
int INF = 0x3f3f3f3f;
int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
int[][] cost = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(cost[i], INF);
}
cost[0][0] = 0;
Deque<int[]> que = new LinkedList<>();
que.add(new int[]{0, 0});
while (!que.isEmpty()) {
int[] p = que.pollFirst();
int x = p[0], y = p[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int g = i + 1 == grid[x][y] ? 0 : 1;
int nc = cost[x][y] + g;
if (nc < cost[nx][ny]) {
cost[nx][ny] = nc;
if (g == 0) {
que.addFirst(new int[]{nx, ny});
} else {
que.addLast(new int[]{nx, ny});
}
}
}
}
}
return cost[m - 1][n - 1];
}
|
3.AStar算法（启发式搜索）
待续…
