{"ID":2845324,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.04345","arxiv_id":"2511.04345","title":"A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2511.04345","url_pdf":"https://arxiv.org/pdf/2511.04345v1","authors":"[\"Kuowen Chen\",\"Nicole Wein\",\"Yiran Zhang\"]","published":"2025-11-06T13:24:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}