# Recent progress on the next-to-shortest-path problem for directed graphs?

In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem:

Let $$G$$ be a directed graph with edge-weighting $$w$$. Let $$u,v$$ be vertices in $$V(G)$$. Let $$p_1$$ be a path of minimum weight from $$u$$ to $$v$$. Compute a simple path $$p_2$$ from $$u$$ to $$v$$ with $$w(p_2) > w(p_1)$$ and such that for any other path $$p$$ from $$u$$ to $$v$$ with $$w(p) > w(p_1)$$, we have $$w(p) \ge w(p_2)$$.

They prove that this problem is NP-hard. Their proof involves choosing a weight function that takes value $$1$$ on a certain edge and $$0$$ elsewhere, so it relies in a fundamental way on the possibility of there being edges of weight $$0$$.

Is anything known about whether the problem remains NP-hard when one restricts to unit-weight graphs, that is graphs for which $$w(e) = 1$$ for each $$e \in E(G)$$?

• We call those unweighted graphs Jun 5 '20 at 3:51
• This paper solves the unweighted problem in $O(n^2)$: A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs Nov 10 '20 at 17:24
• In the Conclusion section of paper referred in the comment of isaacg the authors say: "the time-complexity of the next-to-shortest path problem in digraphs when the edge lengths are required to be strictly positive is still open." Mar 9 at 0:25

Since $$p_2$$ is different from $$p_1$$ on at least one edge, repeatedly remove one edge in $$p_1$$ from the graph and solve the shortest path problem, which would be at worst $$n$$ times the complexity of the shortest path problem.
• And how do you proceed, if all resulting paths have the same weight $w(p_1)$ as the original shortest path $p_1$? Jun 8 '20 at 12:56