分层图最短路径算法详解

在最短路径问题中，我们经常遇到带约束条件的场景——比如“最多允许k次将边权变为0”“最多使用k次加速道具”等，这类问题无法用普通的最短路径算法直接解决，而分层图最短路径算法通过“状态分层”的思想，将带约束的问题转化为普通最短路径问题，成为解决这类场景的核心工具。

一、分层图算法的核心思想

1.1 问题引入：带约束的最短路径

先看一个经典问题：给定一张有向图，边有非负权重，允许最多k次将某条边的权重临时改为0，求从起点到终点的最短路径。

这个问题的关键是“最多k次修改”的约束——普通最短路径算法（如Dijkstra）只能处理固定边权，无法记录“使用了几次修改”的状态。如果直接暴力枚举使用修改的边，当k较大时（比如k=10），复杂度会极高。

1.2 分层图的核心思路

分层图算法的解决思路是：用“分层”的方式记录约束状态，将带约束的问题转化为多层图上的普通最短路径问题。

具体来说：

• 把原图复制成(k+1)层，第t层（t=0,1,…,k）代表“已经使用了t次修改”的状态。
• 层内边：不使用修改，直接沿用原图边权（从第t层的u到第t层的v，边权不变）。
• 层间边：使用1次修改，边权变为0（从第t层的u到第t+1层的v，边权为0，且t+1≤k）。

此时，“从起点到终点，最多使用k次修改”的最短路径，就等价于“从第0层起点到第0~k层终点的最短路径”。

二、分层图的构建方法

2.1 分层图的结构定义

分层图由“层”和“边”两部分组成：

• 层（Layer）：共(k+1)层，编号0到k。第t层的节点表示“到达该节点时，已使用了t次修改”。
• 节点状态：用二元组(u, t)表示“第t层的节点u”，代表“到达u且使用了t次修改”的状态。
• 边的类型：
  • 层内边：在第t层内，从(u, t)到(v, t)，边权与原图中u→v的边权相同（不使用修改）。
  • 层间边：从第t层到第t+1层，从(u, t)到(v, t+1)，边权为0（使用1次修改，且t+1≤k）。

2.2 构建步骤（以“最多k次边权改为0”为例）

1. 初始化分层图：创建(k+1)层，每层包含原图所有节点。
2. 添加层内边：对原图中每条边u→v（权值w），在每层t（0≤t≤k）添加边(u, t)→(v, t)，权值w。
3. 添加层间边：对原图中每条边u→v（权值w），对每层t（0≤t<k）添加边(u, t)→(v, t+1)，权值0（表示使用1次修改）。
4. 定义起点和终点：起点为(s, 0)（起点s，0次修改），终点为所有(t, e)（终点e，t从0到k），最终答案取这些终点的最短路径最小值。

三、分层图最短路径的求解

分层图本质是“带状态的图”，可直接用Dijkstra算法（边权非负时）或SPFA算法（含负权边时）求解，只需将“节点”扩展为“(节点, 层数)”的状态。

3.1 算法步骤

1. 定义距离数组：dist[u][t]表示从起点(s, 0)到(u, t)的最短路径，初始化为无穷大，dist[s][0] = 0。
2. 优先队列：用优先队列（小根堆）存储待处理的状态，按距离从小到大排序，初始加入(s, 0)。
3. 松弛操作：
   • 取出队首状态(u, t)，遍历其所有出边（层内边和层间边）。
   • 对每条边(u, t)→(v, t’)（权值w），若dist[v][t'] > dist[u][t] + w，则更新dist[v][t']并加入队列。
4. 结果提取：终点e的最短路径为min(dist[e][0], dist[e][1], ..., dist[e][k])。

3.2 Java代码实现（以Dijkstra为例）

import java.util.*;public class LayeredGraphShortestPath {// 邻接表：adj[t][u] 存储第t层u的所有出边（v, w）private List<List<List<int[]>>> adj;private int n; // 原图节点数private int k; // 最大使用次数private int INF = Integer.MAX_VALUE / 2; // 避免溢出public LayeredGraphShortestPath(int n, int k) {this.n = n;this.k = k;// 初始化(k+1)层，每层n个节点adj = new ArrayList<>(k + 1);for (int t = 0; t <= k; t++) {List<List<int[]>> layer = new ArrayList<>(n);for (int u = 0; u < n; u++) {layer.add(new ArrayList<>());}adj.add(layer);}}// 添加原图边：u->v，权值wpublic void addEdge(int u, int v, int w) {// 1. 添加层内边（所有层）for (int t = 0; t <= k; t++) {adj.get(t).get(u).add(new int[]{v, w});}// 2. 添加层间边（t从0到k-1）for (int t = 0; t < k; t++) {adj.get(t).get(u).add(new int[]{v, 0}); // 权值改为0，进入t+1层}}// 求解从s到e的最短路径（最多使用k次修改）public int shortestPath(int s, int e) {// dist[t][u]：第t层u的最短距离int[][] dist = new int[k + 1][n];for (int t = 0; t <= k; t++) {Arrays.fill(dist[t], INF);}dist[0][s] = 0;// 优先队列：(距离, 节点u, 层数t)，按距离从小到大PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));pq.add(new int[]{0, s, 0});while (!pq.isEmpty()) {int[] curr = pq.poll();int d = curr[0];int u = curr[1];int t = curr[2];// 已找到更优路径，跳过if (d > dist[t][u]) {continue;}// 到达终点，可提前记录（但需继续找更优解）if (u == e) {// 暂不返回，因为可能有更低的距离在后面}// 遍历当前层u的所有出边for (int[] edge : adj.get(t).get(u)) {int v = edge[0];int w = edge[1];int nextT = t;// 判断是否是层间边：层内边t不变，层间边t+1// （注：层间边是从t到t+1，这里通过原图边添加时已区分，直接计算nextT）// 实际判断：若w是0且原图边权不为0，则是层间边（简化处理：直接根据t是否可+1）if (w == 0 && t < k) {nextT = t + 1;}// 松弛操作if (dist[nextT][v] > d + w) {dist[nextT][v] = d + w;pq.add(new int[]{dist[nextT][v], v, nextT});}}}// 取终点e在所有层的最短距离int minDist = INF;for (int t = 0; t <= k; t++) {minDist = Math.min(minDist, dist[t][e]);}return minDist == INF ? -1 : minDist; // -1表示不可达}// 测试public static void main(String[] args) {// 示例：3个节点，最多1次修改int n = 3, k = 1;LayeredGraphShortestPath graph = new LayeredGraphShortestPath(n, k);// 添加原图边：u->v，权值wgraph.addEdge(0, 1, 5);graph.addEdge(1, 2, 5);graph.addEdge(0, 2, 20);// 求0到2的最短路径（最多1次修改）// 最优路径：0->1（不修改，5），1->2（修改，0），总5+0=5int result = graph.shortestPath(0, 2);System.out.println("最短路径长度：" + result); // 输出5}
}

四、分层图算法的关键细节

4.1 状态表示与空间优化

• 状态定义：核心是(u, t)，其中u是原图节点，t是约束次数（如使用了t次修改）。
• 空间优化：当k较大（如k=100）且n较大（如n=1e4）时，dist[k+1][n]可能占用较多内存（1e4 * 100 = 1e6，可接受），但k超过1e3时需谨慎（可能达1e7级别）。

4.2 边的处理

• 层内边和层间边的区分：无需额外标记，通过“是否修改权值”和“层数t是否增加”判断。
• 重边处理：原图中的重边在分层图中会自然继承，Dijkstra算法会自动选择最优边。

4.3 复杂度分析

• 节点数：分层图共有n*(k+1)个节点。
• 边数：每层有m条层内边，共m*(k+1)；层间边共m*k条，总边数m*(2k+1)。
• 时间复杂度：使用Dijkstra算法（优先队列）时，复杂度为O((n*k + m*k) * log(n*k))，适用于n和k较小的场景（如n=1e3，k=10，复杂度约1e5 * log(1e4) ≈ 1e6，可接受）。

五、典型应用场景

5.1 带次数约束的路径优化

• 免费通行k次：如本文示例，最多k次将边权改为0。
• 边权减半k次：层间边权为原图边权的1/2，层内边权不变。
• 允许k次反向通行：无向图中允许k次从v→u（原图只有u→v），层间边添加v→u。

5.2 状态依赖的路径问题

• 任务调度路径：如“经过k个特定节点后权值变化”，用层数记录经过的特定节点数。
• 动态环境路径：如“前k条边权值不同”，用层数区分路径阶段。

总结
分层图最短路径算法通过“状态分层”将带约束的问题转化为普通最短路径问题，核心是用(节点, 层数)表示状态，用层内边和层间边模拟约束的使用。其优势在于：

• 模型直观：将抽象约束转化为具象的分层结构，容易理解和实现。
• 通用性强：可处理各类次数约束（k次修改、k次特殊操作等）。
  使用时需注意：
• k的大小：k过大时复杂度上升，需结合问题限制（通常k≤1e2）。
• 边权类型：非负边用Dijkstra，含负边用SPFA，但需避免负权回路。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～