深入理解次短路算法：Dijkstra 的扩展与优化

核心逻辑与数学原理

在图论中，次短路（Second Shortest Path）分为非严格次短路与严格次短路。设从源点 $s$ 到汇点 $t$ 的最短路径长度为 $D_{ ext{1st}}$，次短路径长度为 $D_{ ext{2nd}}$：

非严格次短路：允许 $D_{ ext{2nd}} = D_{ ext{1st}}$（此时次短路通常是与最短路长度相同、但边序列不同的另一条路径）。
严格次短路：必须满足 $D_{ ext{2nd}} > D_{ ext{1st}}$。

1. 状态拓扑空间的拆分

传统 Dijkstra 算法在点集 $V$ 上维护一个一维距离向量 $dist[u]$。要求解次短路，必须将状态空间横向扩展为二维：

$dist[u][0]$：源点 $s$ 到节点 $u$ 的最短路长度。
$dist[u][1]$：源点 $s$ 到节点 $u$ 的次短路长度。

2. 堆优化级联松弛原理

次短路的本质是由“最短路的残差边”或者“次短路的出边扩展”递推而来。基于优先队列（小根堆）的 Dijkstra 拓扑扩张同样适用于次短路，其核心数学基石在于状态的二级级联更新。任何一条边 $(u, v)$，其权值为 $w$，在出队时可能触发四种递进的数学状态转化。通过这四种分支，算法可以将任何多余的权值波动流转到 $dist[v][1]$ 中，且总时间复杂度依然稳定在标准的 $O((V+E) ext{log} V)$。

算法推导与状态设计

设当前从优先队列中出队的节点为 $u$，其拓扑路径权值为 $d$（此时 $d$ 可能是最短路，也可能是次短路）。遍历其出边 $(u, v)$，边权为 $w$。定义新候选路径长度 $cost = d + w$。

级联状态转移方程

分支 A：突破当前最短路
若 $cost < dist[v][0]$，说明发现了一条更短的最短路。此时原有 Shortest 退化为 Second Shortest，新路径接管 Shortest。

$$ ext{状态转移}：dist[v][1] = dist[v][0], \\ dist[v][0] = cost$$

注：必须同时将这两个新状态压入优先队列。
分支 B：逼近当前次短路（用于严格次短路判定）
若 $cost > dist[v][0]$ 且 $cost < dist[v][1]$，说明 $cost$ 夹在最短路与次短路之间，直接更新次短路。

$$ ext{状态转移}：dist[v][1] = cost$$
分支 C：非严格次短路特判
若题目要求非严格次短路，且 $cost == dist[v][0]$，虽然它无法更新最短路，但它属于另一条与之并列的路径，有资格更新次短路，触发：$dist[v][1] = cost$。若求严格次短路，此分支必须放弃。

C++ 标准源码（严格次短路标准堆优化模板）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 100005;

struct Edge {
    int to;
    long long weight;
};

struct HeapNode {
    long long d;
    int u;
    int type; // 0 表示当前值是最短路估计，1 表示次短路估计
    bool operator>(const HeapNode& rhs) const {
        return d > rhs.d;
    }
};

std::vector<Edge> adj[MAXN];
long long dist[MAXN][2]; // dist[u][0]: 最短路, dist[u][1]: 次短路
bool vis[MAXN][2];      // 二维标记数组，拦截最短路和次短路的冗余出队

void dijkstra_2nd(int s, int n) {
    for (int i = 1; i <= n; ++i) {
        dist[i][0] = INF;
        dist[i][1] = INF;
        vis[i][0] = false;
        vis[i][1] = false;
    }

    std::priority_queue<HeapNode, std::vector<HeapNode>, std::greater<HeapNode> > pq;

    dist[s][0] = 0;
    pq.push(HeapNode{0, s, 0});

    while (!pq.empty()) {
        HeapNode curr = pq.top();
        pq.pop();

        int u = curr.u;
        int type = curr.type;

        // 致命踩坑点：必须进行二维 vis 校验，否则堆内过期的脏数据会导致复杂度暴涨
        if (vis[u][type]) continue;
        vis[u][type] = true;

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            long long w = adj[u][i].weight;
            long long cost = curr.d + w; // 基于当前出队状态进行路径累加

            // 分支 A：刷新最短路，旧最短路顺延为次短路
            if (cost < dist[v][0]) {
                dist[v][1] = dist[v][0];
                pq.push(HeapNode{dist[v][1], v, 1}); // 旧值降级压入堆

                dist[v][0] = cost;
                pq.push(HeapNode{dist[v][0], v, 0}); // 新最短路压入堆
            }
            // 分支 B：严格夹在最短路与次短路之间，仅更新次短路
            else if (cost > dist[v][0] && cost < dist[v][1]) {
                dist[v][1] = cost;
                pq.push(HeapNode{dist[v][1], v, 1});
            }
            // 若题目要求【非严格次短路】，则取消上面的 cost > dist[v][0] 限制，改为 cost >= dist[v][0] 即可
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        adj[u].push_back(Edge{v, w});
        adj[v].push_back(Edge{u, w}); // 无向图双向建边
    }

    dijkstra_2nd(1, n);

    if (dist[n][1] == INF) {
        std::cout << -1 << "\n";
    } else {
        std::cout << dist[n][1] << "\n"; // 输出汇点 n 的严格次短路
    }

    return 0;
}

NOIP 实战避坑指南

vis 标记数组未开辟二维状态空间：
许多选手直接沿用传统一维 Dijkstra 的 vis[u]。一旦节点 u 的最短路确定并使得 vis[u]=true，后续该节点真正合法的次短路出队状态就会被 if(vis[u]) continue; 粗暴拦截。这导致次短路状态无法继续向后松弛扩散，求出的次短路通常保持为初始值 INF，在评测中直接挂零。
更新最短路时漏掉旧值的“降级下传”：
当触发分支 A 即 cost < dist[v][0] 时，必须先执行 dist[v][1] = dist[v][0] 并在堆中压入 {dist[v][1], v, 1}，再更新 dist[v][0]。如果直接覆盖 dist[v][0] = cost，原本可能成为次短路的最优解会被无情抹去，破坏了状态转移的连续性。

经典 NOIP/洛谷真题

1. 洛谷 P2865 [USACO06NOV] Roadblocks G

题意描述：
给定一个由 $N$ 个点 $M$ 条双向边组成的无向图，求从节点 $1$ 到节点 $N$ 的严格次短路长度。数据保证至少存在一条次短路。
问题本质与核心思路：
标准严格次短路的标杆真题。由于是无向图，且要求严格大于最短路，完美契合二维级联 Dijkstra 算法。核心思路就是利用上述源码的状态转移控制，在松弛条件中严格限制 cost > dist[v][0]。当堆结构处理完毕后，dist[N][1] 存储的即为物理严格次短路。

2. 洛谷 P1491 集合位置

题意描述：
给定一个二维平面上的无向带权图，每个点有坐标，边权为两点间的欧几里得距离。要求找出一条从起点到终点的次短路径，要求次短路径与最短路径不能完全由相同的边组成（即非严格次短路，但路径本身作为边的集合不能与最短路完全重合）。
问题本质与核心思路：
删边法求次短路。
由于此题的数据范围通常较小（$N \le 200$），且要求的是路径形态层面的“次短”。可以先跑一次标准的 Dijkstra 算法求出绝对最短路，并记录下最短路径上经过的所有边（至多 $N-1$ 条）。接着，依次暴力将最短路上的某一条边在邻接表中伪删除（通过标记使其不可通行），每删一条边就跑一次完整的标准单源最短路。在所有删边后的最短路结果中，取出的最小值，本质上就是与原最短路至少有一条边不同的次短路。这种解法巧妙利用了拓扑路径的离散特征，时间复杂度为 $O(N \cdot (V+E)\text{log} V)$，在数据体量适中时常数极小，解题容错率极高。