Given a graph and a pair of terminals $s$, $t$, the next-to-shortest path problem asks for an $s\!\to \!t$ (simple) path that is shortest among all not shortest $s\!\to \!t$ paths (if one exists). This problem was introduced in 1996, and soon after was shown to be NP-complete for directed graphs with non-negative edge weights, leaving open the case of positive edge weights. Subsequent work investigated this open question, and developed polynomial-time algorithms for the cases of undirected graphs and planar directed graphs. In this work, we resolve this nearly 30-year-old open problem by providing an algorithm for the next-to-shortest path problem on directed graphs with positive edge weights.

翻译：给定一个图及一对端点 $s$ 和 $t$，次最短路径问题要求在所有非最短 $s\!\to \!t$ 路径（若存在）中，找到一条最短的 $s\!\to \!t$（简单）路径。该问题于1996年被提出，随后很快被证明对于具有非负边权重的有向图是NP完全的，而正边权重的情况则一直悬而未决。后续研究针对这一开放问题进行了探索，并为无向图及平面有向图的情形提出了多项式时间算法。在本工作中，我们通过为具有正边权重的有向图上的次最短路径问题提供一种算法，解决了这一近30年的开放问题。