We study the computation of a second shortest simple \(s\)–\(t\) path (2-SP) in a directed graph with \(n\) nodes, \(m\) arcs and nonnegative integer arc costs bounded by \(C\). Working with reduced costs and a depth-first search that gives priority to a fixed shortest path \(P_{st}\), every candidate second path is a prefix of \(P_{st}\), a detour, and a suffix of \(P_{st}\), and detours are classified by their re-entry arc as a forward, a cross or a backward. The forward and cross classes are solved exactly in \(O(m+n\log n)\) time by a single multi-source Dijkstra computation. For the backward class we introduce a crossing decomposition: \(O(l/T)\) Dijkstra computations evaluate exactly a class containing every backward detour of a span at least \(T\), where \(l \le n\) is the number of nodes of \(P_{st}\). With \(T=\lceil\sqrt{l}\rceil\) only the narrow core — backward detours of span below \(\sqrt{l}\) — remains, and it is solved exactly by a parametric negative-cycle method with batched branching whose number of rounds adapts to the instance. The complete algorithm is exact, uses \(O(m)\) space, and is never asymptotically worse than the classical \(O(l(m+n\log n))\) one-Dijkstra-per-deviation bound. Finally, under the APSP conjecture, no algorithm solves the narrow core in \(O(m\sqrt {n}\,\mathrm{polylog}(nC))\) time for all polynomially bounded integer costs: the decomposition confines the known hardness of 2-SP to a small, explicitly described class of detours.
Second shortest simple paths in directed graphs: a crossing decomposition and a span-adaptive exact algorithm
\(\)