A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs

Jul 16, 2026

Upload by Patrick

The next-to-shortest path problem, given a directed graph with terminals s and t, seeks a simple s→t path that is shortest among all not-shortest s→t paths, if such a path exists. Introduced in 1996 and shown NP-complete for non-negative weights, it remained open for strictly positive weights. This work resolves the longstanding question by designing the first polynomial-time algorithm for directed graphs with positive edge weights, including an explicit runtime bound and constructive output.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages34

Reading Time1 h 26 min

Introduction

Our Contribution

Related Work

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs Kuowen Chen∗ IIIS, Tsinghua University Nicole Wein† University of Michigan Yiran Zhang‡ IIIS, Tsinghua University arXiv :2511 .04345v2 [ cs .DS] 13 Jul 2026 Abstract Given a graph and a pair of terminals s, t, the next-to-shortest path problem asks for an s→t (simple) path that is shortest among all not shortest s→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 ofundirected graphs and planar directed graphs. In this work, we resolve this nearly 30-yearold open problem by providing an algorithm for the next-to-shortest path problem on directed graphs with positive edge weights. ∗ This work was initiated while the author was at the University [of Michigan.](of Michigan. ckw22@mails.tsinghua.edu.cn)[ ckw22@mails.tsinghua.edu.cn](of Michigan. ckw22@mails.tsinghua.edu.cn)[ ](of Michigan. ckw22@mails.tsinghua.edu.cn)†[nswein@umich.edu](nswein@umich.edu) ‡[zhangyir22@mails.tsinghua.edu.cn](zhangyir22@mails.tsinghua.edu.cn) 1 Introduction Given a directed graph with positive edge weights, and a pair of terminals s, t, the next-to-shortest path problem (also known as the strictly second-shortest path problem) asks for an s→t (simple) path that is shortest among all not shortest s → t paths (if one exists) . We present the first polynomial time algorithm for this problem. The next-to-shortest path problem was first introduced by Lalgudi, Papaefthyrniou, and Potkonjak in 1996 for the application of processing data streams in hardware [LPP96, LPP00] . Soon after, Lalgudi and Papaefthymiou proved that the problem is NP-complete on directed graphs with nonnegative edge weights [LP97], but that there is a polynomial-time algorithm for the relaxation where the path need not be simple. In their NP-hardness reduction, the weight-0 edges play a crucial role, and the case of positive edge weights remained open for almost 30 years until the present work. In the meantime there was a long line of work on the next-to-shortest path problem in undirected graphs. In 2004, Krasikov and Noble gave the first polynomial-time algorithm for the undirected nextto-shortest path problem with positive edge weights [KN04] . (They also conjectured that it is NP-complete for directed graphs; we disprove this conjecture if P NP.) For an n-vertex, m-edge graph, their algorithm ran in time O (n3 m) time, and was subsequently improved by Li, Sun, and Chen to O(n3 ) [LSC06], then by Kao, Chang, Wang, and Juan to O(n2 ) [KCWJ11], and finally by Wu to O(nlog n+m) with the additional guarantee that the path can be found in linear time if the distances from s and t to all other vertices have already been computed [Wu13] . This was extended to non-negative edge weights by Wu, Guo, and Wang [WGW12](see also independent work by Zhang and Nagamochi with larger running time [ZN12]) . Before the general solution was known, the problem was also studied on special classes of graphs [MP06, BMP09] . See also [DHLS14] for a data structure that implicitly represents near-shortest s-t paths. Additionally, the problem of finding an induced not-shortest path is also solvable in polynomial time on unweighted graphs [BSS21] . For directed graphs with positive edge weights, Wu and Wang gave a polynomial-time algorithm of the next-to-shortest path problem when the graph is planar [WW15] . They also proved some properties of a solution for general positively weighted directed graphs. However no further progress was made, and in fact, it was not even known how to find any not-shortest s→t path in polynomial time. At least 11 papers have explicitly stated the open problem solved in this paper: Is the next-

FAQs

What is the next-to-shortest path problem in this paper?

Given a directed graph and terminals s, t, it asks for a simple s→t path that is the shortest among all s→t paths that are not shortest (if such a path exists). The paper also notes it is known as the strictly second-shortest path problem.

Why was the case of positive edge weights challenging?

Lalgudi, Papaefthyrniou, and Potkonjak introduced the problem in 1996, and NP-completeness was shown for directed graphs with non-negative edge weights. The positive edge weights case remained open for nearly 30 years until this work.

What does the main result provide?

The paper gives a polynomial-time algorithm that determines whether a next-to-shortest path from s to t exists and, if so, outputs such a path. It states an explicit time complexity bound in Theorem 1.1.

Jul 16, 2026

Upload by Patrick