当前位置：首页 > news >正文

dj算法与分层图最短路径

news 2025/6/29 0:23:14

dj适用的情景

给定一个源点, 求解源点到每个点的最短路径 (单源最短路径算法)
适用于: 有向图和边的权值不能为负值

此处没有介绍反向索引堆的解法
使用最常用的普通堆 + 建图

模板题(网络延迟时间)

链接: https://leetcode.cn/problems/network-delay-time/description/

题目步骤解析

在这里插入图片描述

开始先将所有点的距离都设为无穷大, 开始所有点都没有使用过, 所以大小先都设为无穷大, 并且之后我们要进行弹出操作, 弹出的点不需要再进行添加, 所以需要 vis 来进行标记操作
接下来将所需源点添加入堆中, 开始 a 到 a 的距离是 0, distance 的位置更新成 0, 进入堆中并弹出, 并将 a 点标记为 true, 将 a 指向的边添加到堆中, 前提是没有被标记过, 并且到那个点的距离要比记录在distance 上的距离要小 , 才可以添加到堆中
当将 a 指向的点全部遍历完, 继续弹出第一个点, 并重复以上操作, 就可以得到一张到 a 到各个点的最短距离的数据, 我们进行遍历, 查找是否存在无穷大, 如果有说明无法到达这个点, 如果没有就说明可以找到最小值

代码(附上解析)

动态建图版

public int networkDelayTime(int[][] times, int n, int k) {// 动态建图ArrayList<ArrayList<int[]>> graph = new ArrayList<>();for(int i = 0;i <= n;i++) {graph.add(new ArrayList<>());}// 0 是出发点, 1 是到达点, 2 是距离for(int[] edge : times) {graph.get(edge[0]).add(new int[]{edge[1],edge[2]});}// 构建路线(多1一个位置是因为0位置我们不使用)int[] distance = new int[n + 1];// 开始标记无穷大Arrays.fill(distance,Integer.MAX_VALUE);// 构造访问的数组, 防止重复访问boolean[] vis = new boolean[n + 1];// 构造小根堆PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);// 源点标记一下距离为 0, 并添加到小根堆中 distance[k] = 0;heap.add(new int[]{k,0});// 当堆中没有元素就退出while (!heap.isEmpty()) {// 弹出首个点, 值已经在之前更新了, 不需要更新, 我们只需要遍历该点到达的地方int u = heap.poll()[0];// 访问过直接跳过这个点if(vis[u]){continue;}// 没弹出过标记一下vis[u] = true;// 开始遍历这个点到达的所有点for (int[] edge : graph.get(u)) {int a = edge[0];// 代表到达点int b = edge[1];// 代表距离// 更新并添加的前提, 到达点未被弹出, 并且从弹出的出发点到达(到达点)的距离要更小才会进行更新if(!vis[a] && distance[u] + b < distance[a]) {distance[a] = distance[u] + b;heap.add(new int[]{a,distance[a]});}}}// 返回值一定要找到最大值, 因为我们存储的是到达每个点的最小距离int ans = Integer.MIN_VALUE;for(int i = 1;i <= n;i++) {// 如果发现无穷大, 无法到达所有点if(distance[i] == Integer.MAX_VALUE) {return -1;}// 更新最大值ans = Math.max(distance[i],ans);}return ans;}

链式前向星

public static int MAXN = 101;
public static int MAXM = 6001;
public static int[] head = new int[MAXN];// 边号 出发点
public static int[] next = new int[MAXM];// 下一个的边号 边号
public static int[] to = new int[MAXM];// 到达点 边号
public static int[] weight = new int[MAXM];// 距离 边号
public static int cnt = 1;
public static int networkDelayTime1(int[][] times, int n, int k) {// 链式前向星建图// 0 是出发点, 1 是到达点, 2 是距离for(int[] edge : times) {build(edge[0],edge[1],edge[2]);}// 构建路线(多1一个位置是因为0位置我们不使用)int[] distance = new int[n + 1];// 开始标记无穷大Arrays.fill(distance,Integer.MAX_VALUE);// 构造访问的数组, 防止重复访问boolean[] vis = new boolean[n + 1];// 构造小根堆PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);// 源点标记一下距离为 0, 并添加到小根堆中distance[k] = 0;heap.add(new int[]{k,0});// 当堆中没有元素就退出while (!heap.isEmpty()) {// 弹出首个点, 值已经在之前更新了, 不需要更新, 我们只需要遍历该点到达的地方int u = heap.poll()[0];// 访问过直接跳过这个点if(vis[u]){continue;}// 没弹出过标记一下vis[u] = true;// 开始遍历这个点到达的所有点// 先从 head 找到该点的第一个边号, 并遍历所有的边号for (int i = head[u]; i != 0; i = next[i]) {int a = to[i];// 代表到达点int b = weight[i];// 代表距离// 更新并添加的前提, 到达点未被弹出, 并且从弹出的出发点到达(到达点)的距离要更小才会进行更新if(!vis[a] && distance[u] + b < distance[a]) {distance[a] = distance[u] + b;heap.add(new int[]{a,distance[a]});}}}// 返回值一定要找到最大值, 因为我们存储的是到达每个点的最小距离int ans = Integer.MIN_VALUE;for(int i = 1;i <= n;i++) {// 如果发现无穷大, 无法到达所有点if(distance[i] == Integer.MAX_VALUE) {return -1;}// 更新最大值ans = Math.max(distance[i],ans);}return ans;
}private static void build(int a, int b, int c) {// 如果 head[a] 开始存着一条边号, 要把它作为下一条边号// 并更新一下 head[a] 的新边号next[cnt] = head[a];head[a] = cnt;// 更新一下这条边对应的点和权值to[cnt] = b;weight[cnt++] = c;
}

静态建图会比动态建图速度快一半

单源最短路径

链接: https://www.luogu.com.cn/problem/P4779
洛谷的测试用例大, 用链式前向星来建图

解析

这里就不多赘述, 因为和上一题基本完全一样, 只是必须要使用链式前向星来建图

代码

import java.io.*;
import java.util.*;public class 单源最短路径 {public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static int MAXN = 100001;public static int MAXM = 200001;public static int[] head = new int[MAXN];public static int[] next = new int[MAXM];public static int[] to = new int[MAXM];public static int[] weight = new int[MAXM];public static int n;public static int m;public static int cnt = 1;public static void main(String[] args) throws IOException{n = in.nextInt();m = in.nextInt();int s = in.nextInt();// 链式前向星建图for (int i = 0; i < m; i++) {int a = in.nextInt();int b = in.nextInt();int c = in.nextInt();addEdge(a,b,c);}// 建立 distance 和 visint[] distance = new int[n + 1];Arrays.fill(distance,Integer.MAX_VALUE);boolean[] vis = new boolean[n + 1];// 源点的距离标记distance[s] = 0;// 堆的建立以及加入源点PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);heap.offer(new int[]{s,0});while (!heap.isEmpty()) {// 弹出第一个点, 获取到达点的值int u = heap.poll()[0];if (vis[u]) {continue;}vis[u] = true;// 遍历图更新 distance 并加入堆中for (int i = head[u]; i != 0; i = next[i]) {int a = to[i]; // 到达点int b = weight[i]; // 距离// 没访问过并且要小于到达点的距离if (!vis[a] && distance[u] + b < distance[a]) {distance[a] = distance[u] + b;heap.offer(new int[]{a, distance[a]});}}}// 打印for (int i = 1; i <= n; i++) {out.print(distance[i] + " ");}out.close();}private static void addEdge(int a, int b, int c) {next[cnt] = head[a];head[a] = cnt;to[cnt] = b;weight[cnt++] = c;}public static class Read{StringTokenizer st = new StringTokenizer("");BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException{while(!st.hasMoreTokens()){st = new StringTokenizer(bf.readLine());}return st.nextToken();}String nextLine() throws IOException{return bf.readLine();}int nextInt() throws IOException{return Integer.parseInt(next());}long nextLong() throws IOException{return Long.parseLong(next());}double nextDouble() throws IOException{return Double.parseDouble(next());}}
}

可以优化的地方是使用反向索引堆, 自己建堆时间还可以更快一点

最小体力消耗路径

链接: https://leetcode.cn/problems/path-with-minimum-effort/description/

题目解析

在这里插入图片描述
想象成dj问题, 源点到每个点的最小距离, 转化成整条路径的最大距离, 所以我们更新 distance 的距离的时候, 需要先对出发点和到达点的位置相减, 然后与出发点的最小距离进行比较, 也就是

int nc = Math.max(Math.abs(heights[a][b] - heights[x][y]),c);

这是和之前唯一不同的地方, 以及需要加入 bfs 来进行层度优先遍历来进行搜索

代码

import java.util.Arrays;
import java.util.PriorityQueue;public class 最小体力消耗路径_dj {public static int[] move = {1,0,-1,0,1};public int minimumEffortPath(int[][] heights) {// 先求出 n 和 m 方便使用// 分析求出源点到每个点的最小距离int n = heights.length;int m = heights[0].length;// 源点到每个点的最短距离, 更新的时候要更新成路径的最大值int[][] distance = new int[n][m];for(int[] a : distance){Arrays.fill(a,Integer.MAX_VALUE);}// 源点的距离distance[0][0] = 0;// 标记路线是否走过boolean[][] vis = new boolean[n][m];PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2] - b[2]);heap.add(new int[]{0,0,0});while (!heap.isEmpty()) {int[] t = heap.poll();int a = t[0]; // iint b = t[1]; // jint c = t[2]; // 距离也就是到每个点需要的代价// 剪枝, 找到该点直接返回即可if(a == n - 1 && b == m - 1){return c;}// 访问过的点不再访问if (vis[a][b]) {continue;}vis[a][b] = true;// 上下左右四个方向移动for (int i = 0; i < 4; i++) {int x = a + move[i];// 横坐标int y = b + move[i + 1];// 纵坐标// 先判断是否越界if(x >= 0 && y >= 0 && x < n && y < m && !vis[x][y]){// 更新一下该路径的最大值int nc = Math.max(Math.abs(heights[a][b] - heights[x][y]),c);// 如果该点小于存储的距离, 更新并丢到堆中if(nc  < distance[x][y]){distance[x][y] = nc;heap.offer(new int[]{x,y,distance[x][y]});}}}}// 都找不到就返回 -1, 理论上一定可以找到, 防止编译器报错return -1;}
}

水位上升的泳池中游泳

链接: https://leetcode.cn/problems/swim-in-rising-water/description/

题目解析

题目和上一题基本完全一样, 唯一的区别就是此次的源点距离不为 0 (我开始就错了), 因为要等 t 时刻到达源点的高度才可以开始向各个方向移动, 其他与上一题一般无二, 可以来练练手

代码

import java.util.Arrays;
import java.util.PriorityQueue;public class 水位上升的泳池中游泳 {public static int[] move = {1,0,-1,0,1};public int swimInWater(int[][] grid) {// 构造一下距离和 visint n = grid.length;int m = grid[0].length;int[][] distance = new int[n][m];for (int[] a : distance){Arrays.fill(a,Integer.MAX_VALUE);}boolean[][] vis = new boolean[n][m];distance[0][0] = 0;PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2]-b[2]);heap.offer(new int[]{0,0,grid[0][0]});while (!heap.isEmpty()) {int[] t = heap.poll();int a = t[0]; // iint b = t[1]; // jint c = t[2]; // 到 b 点所需要的代价if (a == n - 1 && b== m - 1) {return c;}if (vis[a][b]) {continue;}vis[a][b] = true;for (int i = 0; i < 4; i++) {int x = a + move[i];int y = b + move[i + 1];if (x >= 0 && y >= 0 && x < n && y < m && !vis[x][y]) {int nc = Math.max(grid[x][y],c);if(nc < distance[x][y]) {distance[x][y] = nc;heap.offer(new int[]{x,y,nc});}}}}return -1;}
}

分层图最短路径先欠一下

不把实际位置看做图上的点，而是把实际位置及其状态的组合看做是图上的点, 然后搜索 bfs 或者 dj 的过程不变, , 只是扩了点(分层)而已原理简单, 核心在于如何扩点、如何到达、如何算距离, 每个题可能都不一样

获取所有钥匙的最短路径

链接: https://leetcode.cn/problems/shortest-path-to-get-all-keys/description/

题目分析

在这里插入图片描述
以一个我之前一直通不过的一个用例来大概讲解一下题目思路

开始时字符串数组, 我们需要先转化成字符数组比较好操作, 顺带找到源点, 并找到钥匙
此处钥匙的状态我们使用 int 的前 6 位来进行标记, 1 为有钥匙, 0 为没钥匙
然后分层图遍历, 相当于点可以重复走, 但是此时你的状态要是不同, 如上图, 当你拿到了钥匙 b, 你可以选择往回走, 因为你没钥匙的时候走到 b 格子, 和有钥匙的时候走回去 @ 格子, 是不一样的状态, 这是分层图最短路径的核心, 最关键就是状态不一样
然后我们对走到各种格子的情况进行划分
- 走到 . 格子, 直接标记并添加队列即可
- 走到 # 格子, 不可以走, 标记一下
- 走到锁的话, 查看一下手上有没有钥匙, 如果有钥匙就添加队列并标记
- 走到钥匙的话, 把钥匙的状态更新一下, 然后看一下是否已经拿到所有钥匙了, 拿到了就返回, 没拿到就标记加上添加到队列里
- 走到 @ 格子, 只需要看一下有没有走过即可, 状态不同就可以走, 并标记

代码

public class 获取所有钥匙的最短路径 {public static int MAXN = 31;public static char[][] grid = new char[3][5];public static boolean[][][] vis = new boolean[3][5][64];public static int[][] queue = new int[3 * 5 * 64][3];public static int n,m;public static int l,r;public static int[] move = {1,0,-1,0,1};public static int shortestPathAllKeys(String[] grids) {n = grids.length;m = grids[0].length();l = r = 0;int keys = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = grids[i].charAt(j);if (grid[i][j] == '@') {add(i, j, 0);vis[i][j][0] = true;}if (grid[i][j] >= 'A' && grid[i][j] <= 'F') {keys |= (1 << (grid[i][j] - 'A'));}}}int ans = 0;while (l < r) {int size = r - l;ans++;while (size-- > 0) {int[] t = queue[l++];int a = t[0];int b = t[1];int c = t[2];for (int i = 0; i < 4; i++) {int x = a + move[i];int y = b + move[i + 1];if (x >= 0 && y >= 0 && x < n && y < m && !vis[x][y][c]) {// 找到空房间if (grid[x][y] == '.') {add(x, y, c);vis[x][y][c] = true;} else if (grid[x][y] >= 'A' && grid[x][y] <= 'F') {// 找到锁if (((1 << (grid[x][y] - 'A')) & c) != 0) {add(x, y, c);}vis[x][y][c] = true;} else if (grid[x][y] >= 'a' && grid[x][y] <= 'f') {int nc = (1 << (grid[x][y] - 'a')) | c;if (nc == keys) {return ans;}add(x, y, nc);vis[x][y][nc] = true;} else if (grid[x][y] == '#') {vis[x][y][c] = true;} else if (grid[x][y] == '@') {add(x,y,c);vis[x][y][c] = true;}}}}}for (int i = 0; i < r; i++) {System.out.println("第" + (i + 1) +"次 "+ "i = " + queue[i][0] + " ,j = " + queue[i][1] + ",c = "+ queue[i][2]);System.out.println();}return -1;}private static void add(int i, int j, int k) {queue[r][0] = i;queue[r][1] = j;queue[r++][2] = k;}public static void main(String[] args) {String[] grid = {"@...a",".###A","b.BCc"};System.out.println(shortestPathAllKeys(grid));}}

优雅一点版本代码

public static int MAXN = 31;
public static char[][] grid = new char[3][5];
public static boolean[][][] vis = new boolean[3][5][64];
public static int[][] queue = new int[3 * 5 * 64][3];
public static int n,m;
public static int l,r;
public static int[] move = {1,0,-1,0,1};
public static int shortestPathAllKeys(String[] grids) {n = grids.length;m = grids[0].length();l = r = 0;// 找到钥匙, 因为钥匙只有 6 把, 所以使用 int 的前 6 位来进行表示int keys = 0;// 字符串数组太恶心了, 使用填一下表格, 并找出所有的钥匙, 并添加源点到队列里for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = grids[i].charAt(j);if (grid[i][j] == '@') {add(i, j, 0);// 标记这个点已经走过了vis[i][j][0] = true;}if (grid[i][j] >= 'A' && grid[i][j] <= 'F') {// 位运算添加keys |= (1 << (grid[i][j] - 'A'));}}}// 最终的结果int ans = 0;while (l < r) {int size = r - l;ans++;int a,b,c;while (size-- > 0) {a = queue[l][0]; // 坐标 ib = queue[l][1]; // 坐标 jc = queue[l++][2]; // 钥匙的状态for (int i = 0; i < 4; i++) {int x = a + move[i];int y = b + move[i + 1];int nc = c;if (x < 0 || y < 0 || x == n || y == m || vis[x][y][c] || grid[x][y] == '#') {// 遇到墙或者是越界continue;}if (grid[x][y] >= 'A' && grid[x][y] <= 'F' && ((1 << (grid[x][y] - 'A')) & nc) == 0) {// 找到锁没有对应的钥匙continue;}if (grid[x][y] >= 'a' && grid[x][y] <= 'f') {// 是一把锁nc = (1 << (grid[x][y] - 'a')) | c;}if (nc == keys) {return ans;}if (!vis[x][y][c]) {add(x, y, nc);}}}}return -1;
}