单源次短路算法 - NOI提高级教程

📖 算法原理：双值状态机松弛

单源次短路问题是指在给定加权图中，寻找从起点到其余各点长度仅次于最短路的第二短简单路径的长度。

📐 核心松弛分裂定理

我们用 dist1[v] 表示起点到 $v$ 的最短路，用 dist2[v] 表示起点到 $v$ 的次短路。当利用边 $(u, v)$ (权值为 $w$) 松弛节点 $v$ 时，将产生以下三种分裂情况：

第一种：发现更短的路径 (更新 $d_1$)：
若 dist1[u] + w < dist1[v]，这说明原先的最短路径被超越！原最短路自动“退化”为次短路：
$dist2[v] = dist1[v]$
$dist1[v] = dist1[u] + w$
将两个状态更新同时压入优先队列中。
第二种：发现介于最短与次短之间的路径 (更新 $d_2$)：
若 dist1[u] + w > dist1[v] 且 dist1[u] + w < dist2[v]：
$dist2[v] = dist1[u] + w$
将次短状态更新压入优先队列。
第三种：利用已知的次短路更新次短路：
若 dist2[u] + w < dist2[v]：
$dist2[v] = dist2[u] + w$
将次短状态更新压入优先队列。

演示速度：

点击"开始演示"或"单步执行"观察最短路 $d_1$ 遭到超越退化为次短路 $d_2$ 的物理分裂流程。

🌾 priority_queue 优先队列 [存储结构: (顶点, 路径值, 类型)]

起点 Node 1Start

终点 Node 5 最短距离 d1INF

终点 Node 5 次短距离 d2INF

struct State {
    int id, d, type; // type: 1 最短, 2 次短
    bool operator<(const State& o) const { return d > o.d; }
};

void getSecondShortest() {
    fill(d1, d1 + n + 1, INF); fill(d2, d2 + n + 1, INF);
    d1[start] = 0;
    priority_queue<State> pq;
    pq.push({start, 0, 1});
    
    while (!pq.empty()) {
        auto [u, d, type] = pq.top(); pq.pop();
        if (d > (type == 1 ? d1[u] : d2[u])) continue;
        
        for (auto edge : adj[u]) {
            int v = edge.v, w = edge.w;
            if (d1[v] > d + w) { // 情况 1：超越最短，退化为次短
                d2[v] = d1[v];
                d1[v] = d + w;
                pq.push({v, d1[v], 1});
                pq.push({v, d2[v], 2});
            } else if (d1[v] < d + w && d2[v] > d + w) { // 情况 2：介于中间
                d2[v] = d + w;
                pq.push({v, d2[v], 2});
            }
        }
    }
}

📋 次短路松弛历史步骤日志