Recent progress on the next-to-shortest-path problem for directed graphs?
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.