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算法只适用于权重为非负数的带权图!
p4

或者和BFS进行类比,BFS是每次走1步,如果当路径很长时显然不现实;

因此,Dijkstra算法每次迭代是以节点作为单元,通常为了节省时间我们会用堆(TreeSet?) 来优化

总的时间复杂度为:O(NlogN) 空间复杂度:O(N) 其中N为边数

p5

以上图为例,从节点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.如果边权不是上述情况,只能在弹出的时候标记访问,只有在弹出时才可以确定起点到该点的最短路径。

p6
p7

参考:

1.Dijkstra图解动画:【算法】最短路径查找—Dijkstra算法_哔哩哔哩_bilibili

2.三叶姐的最短路径模板(背下来)三叶姐最短路模板

3.自己写的答案与例题:743. 网络延迟时间

4.矩阵型Dijkstra参考:

675. 为高尔夫比赛砍树

2290. 到达角落需要移除障碍物的最小数目

1368. 使网格图至少有一条有效路径的最小代价

标准模板(矩阵型的图可以将二维(x,y)坐标压缩成一维m*x+y):

class Solution {
public int minCost(int[][] grid) {
/*
最短路算法:
我们先别被箭头迷惑了,先把所有路都当做可以走,不过要走到下一个节点的代价增加了而已
看到了这一点那么这题就可以转化为最短路径的题目
网格中某个点grid[i][j]每次可以往上下左右走一格
1.如果走的方向与原来的方向不一致则消耗一次改格子的次数,cost++
2.如果走的方向与原来的方向一致则不消耗次数,cost不变
求到达grid[m-1][n-1]消耗的最少次数(最小代价、最短路径)
因为代价只有0和1两种,因此既可以用Dijkstra算法,又可以用01BFS
*/
// 解法1:Dijkstra算法
int m = grid.length, n = grid[0].length;
int INF = 0x3f3f3f3f;
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
boolean[][] vis = new boolean[m][n];
int[][] cost = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(cost[i], INF);
}
cost[0][0] = 0;
// 根据到起点的最短距离升序(注意最好不要根据cost直接排序,因为cost会随时改变,弹出时会有出错风险)
// 也就是说你的cost改变了后,pq里面放在头部的元素可能还未来得及改变,因此最好的比较的变量独立且不会被修改
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.add(new int[]{0, 0, 0});
while (!pq.isEmpty()) {
int[] p = pq.poll();
int x = p[1], y = p[2];
if (vis[x][y]) continue; // 访问过就跳过
vis[x][y] = true; // 当且仅当弹出才能确定起点到达改点的最小代价,标记为true
for (int i = 0; i < 4; i++) {
int nx = x + dirs[i][0], ny = y + dirs[i][1];
// 在区域内才需要计算,这里不用保证未访问过,因为前面的路是新的
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
// 只有方向对才不用付出代价,否则要付出代价
int g = i + 1 == grid[x][y] ? 0 : 1;
// nc为起点经过grid[x][y]到达grid[nx][ny]的最小代价
int nc = cost[x][y] + g;
// 小于原来的cost[nx][ny]就可以更新并入队
if (nc < cost[nx][ny]) {
cost[nx][ny] = nc;
pq.add(new int[]{nc, nx, ny});
}
}
}
}
return cost[m - 1][n - 1];
}
}

注意自定义比较规则时候的一些细节:

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> cost[a[0]][a[1]));

//根据到起点的最短距离升序(注意最好不要根据cost直接排序,因为cost会随时改变,弹出时会有出错风险)
//也就是说你的cost改变了后,pq里面放在头部的元素可能还未来得及改变,因此最好的比较的变量独立且不会被修改
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——附详解典例

class Solution {
public int minimumObstacles(int[][] grid) {
/*
01BFS解法:
本题相当于求从grid[0,0]到grid[m-1][n-1]的最短路径(最低成本),其中经过障碍物成本为1,空地成本为0
用常规的堆优化Dijkstra解法时间复杂度为O(m*n*log(m*n))
利用01BFS可以将时间复杂度降为O(m*n),也就是说每个节点只入队1次,不会重复访问且可以在O(1)内找到最短距离的节点
过程为:用一个双端队列维护入队元素,然后如果下一个格子为0可以进入队头,否则进入队尾
同时利用一个dis二维数组维护起点蔓延到该点的最短距离,最后返回dis[m-1][n-1]就是所求
时间复杂度:O(m*n) 空间复杂度:O(m*n)
*/
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]; // dis[i][j]维护起点蔓延到grid[i][j]时的最短距离
for (int i = 0; i < m; i++) {
Arrays.fill(dis[i], INF);
}
dis[0][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; // dis[nx][ny]继承小的值
// 看当前格子为0就入队头,否则入队尾
if (grid[nx][ny] == 0) {
que.addFirst(new int[]{nx, ny});
} else {
que.addLast(new int[]{nx, ny});
}
}
}
}
}
return dis[m - 1][n - 1];
}
}
public int minCost(int[][] grid) {
/*
最短路径算法:
我们先别被箭头迷惑了,先把所有路都当做可以走,不过要走到下一个节点的代价增加了而已
看到了这一点那么这题就可以转化为最短路径的题目
网格中某个点grid[i][j]每次可以往上下左右走一格
1.如果走的方向与原来的方向不一致则消耗一次改格子的次数,cost++
2.如果走的方向与原来的方向一致则不消耗次数,cost不变
求到达grid[m-1][n-1]消耗的最少次数(最小代价、最短路径)
因为代价只有0和1两种,因此既可以用Dijkstra算法,又可以用01BFS
*/
// 解法2:01BFS
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;
// nc为起点经过grid[x][y]到达grid[nx][ny]的最小代价
int nc = cost[x][y] + g;
// 小于原来的cost[nx][ny]就可以更新并入队
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算法(启发式搜索)

待续…