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 restricted to unweighted digraphs, that is directed graphs for which $$w(e) = 1$$ for each $$e \in E(G)$$?

EDIT: The variant in undirected graphs, and the variant where the goal is to find a (not-necessarily simple) walk (as opposed to a path), are known to be in P. Here's a summary:

graph type edge weights path or walk? result paper
directed non-negative path NP-hard [1997]
either non-negative walk in P [1997]
DAG non-negative path = walk in P [1997]
undirected non-negative path in P [2004, 2006, 2011, 2012a,b]
directed strictly positive path open [2011,2015]

(Note that there is also a separate body of work on fast algorithms for finding $$k\ge 2$$ shortest paths, e.g. [1998], where distinct path lengths are not required.)

• We call those unweighted graphs Jun 5, 2020 at 3:51
• My first intuition is certainly naive. What's wrong with it? 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.
– NYD
Jun 8, 2020 at 12:09
• 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, 2020 at 12:56
• This paper solves the unweighted problem in $O(n^2)$: A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs Nov 10, 2020 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, 2021 at 0:25