NeFut Logo NeFut
中 Admin Login

Deep Understanding of Second Shortest Path Algorithm: Extensions and Optimizations of Dijkstra

Published at: 2026-05-29 01:15 Last updated: 2026-06-06 13:04
#algorithm #C++ #Graph

Core Logic and Mathematical Principles

In graph theory, the second shortest path is divided into non-strict second shortest path and strict second shortest path. Let the length of the shortest path from the source $s$ to the sink $t$ be $D_{ ext{1st}}$, and the length of the second shortest path be $D_{ ext{2nd}}$:

1. Splitting the State Topology Space

The traditional Dijkstra algorithm maintains a one-dimensional distance vector $dist[u]$ on the vertex set $V$. To solve the second shortest path, the state space must be expanded horizontally to two dimensions:

2. Heap Optimization Cascade Relaxation Principle

The essence of the second shortest path is derived from the "residual edges of the shortest path" or the "outgoing edges of the second shortest path". The Dijkstra topology expansion based on a priority queue (min-heap) also applies to the second shortest path, with its core mathematical foundation being the secondary cascading update of states. Any edge $(u, v)$ with weight $w$ may trigger four progressive mathematical state transformations when dequeued. Through these four branches, the algorithm can transfer any excess weight fluctuations to $dist[v][1]$, while the overall time complexity remains stable at the standard $O((V+E) ext{log} V)$.

Algorithm Derivation and State Design

Let the current node dequeued from the priority queue be $u$, and its topological path weight be $d$ (at this time $d$ may be the shortest path or the second shortest path). Traverse its outgoing edges $(u, v)$, with edge weight $w$. Define the new candidate path length as $cost = d + w$.

Cascade State Transition Equations

  1. Branch A: Breakthrough Current Shortest Path
    If $cost < dist[v][0]$, it indicates that a shorter shortest path has been found. In this case, the original Shortest degenerates into Second Shortest, and the new path takes over Shortest.

    $$ ext{State Transition}: dist[v][1] = dist[v][0], \\ dist[v][0] = cost$$

    Note: Both of these new states must be pushed into the priority queue.

  2. Branch B: Approaching Current Second Shortest Path (for strict second shortest path determination)
    If $cost > dist[v][0]$ and $cost < dist[v][1]$, it indicates that $cost$ is sandwiched between the shortest path and the second shortest path, and the second shortest path is updated directly.

    $$ ext{State Transition}: dist[v][1] = cost$$

  3. Branch C: Special Case for Non-Strict Second Shortest Path
    If the problem requires non-strict second shortest path, and $cost == dist[v][0]$, although it cannot update the shortest path, it belongs to another path parallel to it and is qualified to update the second shortest path, triggering: $dist[v][1] = cost$. If strict second shortest path is required, this branch must be abandoned.

C++ Standard Source Code (Strict Second Shortest Path Standard Heap Optimization Template)

#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 indicates current value is the shortest path estimate, 1 indicates second shortest path estimate
    bool operator>(const HeapNode& rhs) const {
        return d > rhs.d;
    }
};

std::vector<Edge> adj[MAXN];
long long dist[MAXN][2]; // dist[u][0]: shortest path, dist[u][1]: second shortest path
bool vis[MAXN][2];      // Two-dimensional marking array, intercepting redundant dequeuing of shortest and second shortest paths

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;

        // Fatal pitfall: Must perform two-dimensional vis check, otherwise stale data in the heap will cause complexity to skyrocket
        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; // Path accumulation based on current dequeued state

            // Branch A: Refresh shortest path, old shortest path becomes second shortest path
            if (cost < dist[v][0]) {
                dist[v][1] = dist[v][0];
                pq.push(HeapNode{dist[v][1], v, 1}); // Push old value downgrade into heap

                dist[v][0] = cost;
                pq.push(HeapNode{dist[v][0], v, 0}); // Push new shortest path into heap
            }
            // Branch B: Strictly sandwiched between shortest and second shortest paths, only update second shortest path
            else if (cost > dist[v][0] && cost < dist[v][1]) {
                dist[v][1] = cost;
                pq.push(HeapNode{dist[v][1], v, 1});
            }
            // If the problem requires **non-strict second shortest path**, then cancel the cost > dist[v][0] restriction above, change it to 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}); // Build edges bidirectionally for undirected graph
    }

    dijkstra_2nd(1, n);

    if (dist[n][1] == INF) {
        std::cout << -1 << "\n";
    } else {
        std::cout << dist[n][1] << "\n"; // Output strict second shortest path to sink n
    }

    return 0;
}

NOIP Practical Pitfall Guide

  1. The vis marking array is not allocated in two-dimensional state space:
    Many contestants directly use the traditional one-dimensional Dijkstra's vis[u]. Once the shortest path of node u is determined and vis[u]=true, subsequent legitimate second shortest path dequeue states of that node will be brutally intercepted by if(vis[u]) continue;. This leads to the inability of the second shortest path state to continue relaxing forward, and the second shortest path obtained usually remains at the initial value INF, resulting in a direct zero in the evaluation.
  2. Missing the "downgrade propagation" of the old value when updating the shortest path:
    When triggering Branch A, i.e., cost < dist[v][0], it is necessary to first execute dist[v][1] = dist[v][0] and push {dist[v][1], v, 1} into the heap, and then update dist[v][0]. If dist[v][0] = cost is directly overwritten, the originally optimal solution that could become the second shortest path will be ruthlessly erased, destroying the continuity of state transitions.

Classic NOIP/Luogu Real Questions

1. Luogu P2865 [USACO06NOV] Roadblocks G

2. Luogu P1491 Set Position

Original Source: local://10.3
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS