The directed next-to-shortest path problem was solved by 2 undergrads! arxiv.org/abs/2511.04345 Look out for Kuowen Chen and Yiran Zhang this PhD application cycle.
arxiv.org
A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
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). Thi...