Which algorithm can I use to find the next to shortest path in a graph?

Question

I want to find the next shortest path between 2 vertices in a graph and the path has a positive cost.The next shortest path is allowed to share edges of the shortest path .Which algorithm can I use?

Answer 1

Use the K-shortest path algorithm, where k=2 for you, some sample reference:

Finding the k shortest paths. D. Eppstein. 35th IEEE Symp. Foundations of Comp. Sci., Santa Fe, 1994, pp. 154-165. Tech. Rep. 94-26, ICS, UCI, 1994. SIAM J. Computing 28(2):652-673, 1998.

http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-26.pdf

Answer 2

I doubt this is optimal in terms of running time but:

1. Use Dijkstra's algorithm on graph G to get path P
2. For all edges E in path P:
3. -- If G - E is not connected, continue for next edge (go to 2)
4. -- Use Dijkstra's algorithm on G - E to find path X_i
5. -- If length of current X_i is shorter than all other X_i, save it
6. The X_i at the end of the for loop is the second shortest path

The second-shortest path can't go through all edges in P, but it could go through all but one of them, potentially. I assume by "second-shortest" that you don't use edges more than once, otherwise the second-shortest path could contain P.