6.10 次短路径

---

1. 次短路径简介

次短路径（Second Shortest Path）：指从起点到终点的所有简单路径中，路径总权值严格大于最短路径、且在此条件下最小的那条路径。

次短路径的本质，是在所有从起点到终点的路径中，找到一条「长度严格大于最短路径」但又尽可能短的路径。换句话说，最短路径是最优解，次短路径则是在排除所有最优解（即所有与最短路径等长的路径）后，找到的次优解。

这种问题在实际生活和工程中非常常见，主要应用于需要「备用方案」或「容错能力」的场景。例如：

• 网络路由：当主路由失效时，快速切换到次短路径，保证数据传输不中断。
• 交通导航与物流：为司机或配送员提供绕行路线，规避拥堵或突发状况。
• 通信网络：设计冗余链路，提高网络的健壮性和可靠性。
• 算法竞赛：常见「求第 2 优解」类问题，或需要多方案备选时。

注意：本文默认边权非负（与 Dijkstra 条件一致）。如果有负权边，请使用适配的算法并谨慎处理。

2. 次短路径常见解法

在实际问题中，寻找次短路径（即严格大于最短路径的最优路径）通常需要对经典的最短路算法进行适当扩展。最常用且高效的方法是基于 Dijkstra 算法的变体。

2.1 扩展版 Dijkstra 的核心思路

扩展版 Dijkstra 的核心思路：

在使用优先队列寻找最短路的过程中，同时为每个节点记录两条路径长度：一条是目前已知的最短路径，另一条是比最短路径严格更长、但次优的路径。每次处理节点时，尝试用新路径更新这两条记录：如果新路径比当前最短路径还短，就把原最短路径作为次短路径，并更新最短路径；如果新路径介于最短和次短之间，就更新次短路径。其余情况直接跳过。最终，终点的次短路径记录就是所求答案。

这种方法思路清晰、实现简单，是解决次短路径问题的主流方案。

2.2 扩展版 Dijkstra 的具体步骤

1. 初始化 $dist1$ 和 $dist2$ 数组，全部赋值为无穷大（表示尚未到达）。
2. 将起点的 $dist1$ 设为 $0$，并将起点以距离 $0$ 加入优先队列。
3. 每次从优先队列中取出距离最小的节点 $u$。
4. 枚举 $u$ 的所有邻接节点 $v$，尝试用 $u$ 的当前路径更新 $v$ 的最短和次短距离：
   • 如果新路径长度小于 $dist1[v]$，则将 $dist1[v]$ 的原值赋给 $dist2[v]$，并用新路径更新 $dist1[v]$，同时将 $v$ 及其新距离加入队列。
   • 如果新路径长度介于 $dist1[v]$ 与 $dist2[v]$ 之间（即 $dist1[v] <$ 新路径 $< dist2[v]$），则用新路径更新 $dist2[v]$，并将 $v$ 及其新距离加入队列。
5. 算法结束后，$dist2[target]$ 即为所求的次短路径长度（如果为无穷大则表示不存在）。

2.3 扩展版 Dijkstra 的代码实现

import heapq
from collections import defaultdict

def second_shortest_path(n, edges, s, t):
    """
    求解有向/无向图中从 s 到 t 的次短路径长度（严格大于最短路径的最小路径）。
    参数说明：
        n: 节点数（编号 0 ~ n - 1）
        edges: List[(u, v, w)]，每条边 (u, v, w) 表示 u 到 v 有一条权重为 w 的边
        s: 起点编号
        t: 终点编号
    返回：
        s 到 t 的次短路径长度，若不存在返回 float('inf')
    注意：
        - 默认边权非负
        - 如果为无向图，请取消 graph[v].append((u, w))的注释
    """
    # 构建邻接表
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        # 如果是无向图，取消下行注释
        # graph[v].append((u, w))

    INF = float('inf')
    dist1 = [INF] * n  # dist1[i]：s 到 i 的最短路径长度
    dist2 = [INF] * n  # dist2[i]：s 到 i 的严格次短路径长度

    dist1[s] = 0
    # 优先队列，元素为(当前路径长度, 节点编号)
    pq = [(0, s)]

    while pq:
        d, u = heapq.heappop(pq)
        # 剪枝：如果当前弹出的距离已大于该点的次短路，则无需处理
        if d > dist2[u]:
            continue
        # 遍历 u 的所有邻居
        for v, w in graph[u]:
            nd = d + w  # 新的路径长度
            # 如果找到更短的路径，更新最短和次短
            if nd < dist1[v]:
                dist2[v] = dist1[v]
                dist1[v] = nd
                heapq.heappush(pq, (dist1[v], v))
            # 如果新路径严格介于最短和次短之间，更新次短
            elif dist1[v] < nd < dist2[v]:
                dist2[v] = nd
                heapq.heappush(pq, (dist2[v], v))
            # 其他情况（如 nd 等于 dist1[v] 或大于等于 dist2[v]）无需处理

    return dist2[t]  # 如果为 INF 表示不存在次短路径

2.4 扩展版 Dijkstra 算法分析

• 时间复杂度：$O((V + E)\log V)$，其中 $V$ 是节点数，$E$ 是边数。与 Dijkstra 同阶，常数略大，因为每点维护两条距离。
• 空间复杂度：$O(V)$，用于存储距离数组和优先队列。

3. 进阶与常见问题

3.1 无权图 / 单位权图的次短路径

对于无权图或所有边权均为 $1$ 的单位权图，求次短路径时可以采用 BFS（广度优先搜索）思想，同样维护两个距离数组：$dist1$ 表示最短路径，$dist2$ 表示严格次短路径。使用普通队列按层推进，每当遇到更短路径或介于最短和次短之间的路径时，及时更新对应的距离并将节点入队。整体实现思路与扩展版 Dijkstra 类似，只是优先队列换成了普通队列。

3.2 与 K 短路问题的关系

次短路径实际上是 K 短路问题在 $K = 2$ 时的特例。经典的 K 短路算法有 Yen 算法、Eppstein 算法等，但在 $K = 2$ 的场景下，直接用「扩展版 Dijkstra 维护两条距离」往往更简单高效，代码实现也更直观。

3.3 常见易错点与细节说明

• 严格大于最短路径：次短路径必须严格大于最短路径。如果不存在严格大于最短路径的方案，应返回 $-1$。如果题目允许等长但不同路径作为次短路径，需根据题意调整实现。
• 松弛顺序问题：当 nd < dist1[v] 时，必须先将原有的 dist1[v] 赋值给 dist2[v]，再更新 dist1[v]，否则会丢失正确的次短路径信息。
• 重复 / 等长路径处理：当 nd == dist1[v] 时，通常不应更新 dist2[v]（除非题目特别说明等长但不同路径也算次短路径）。
• 边权要求：本算法默认所有边权为非负。如果存在负权边，需使用 Bellman-Ford 算法的变体，并仔细验证实现的正确性。
• 有向图与无向图的区别：注意区分有向图和无向图。对于无向图，构图时每条边需正反各加入一次，避免遗漏路径。

练习题目

• 2045. 到达目的地的第二短时间

• 次短路径题目列表