Finding second shortest path in a graph(With Backtracking)

Question

I found a problem in LightOJ where the problem was to find the second shortest path in a graph from node 1 to node n(There are n nodes in the graph marked from 1 to n). Now, the problem stated that I can backtrack to find a second shortest path. One of the sample cases is like this:

• Edge from node 1 to 2, cost 100.
• Edge from node 2 to 3, cost 300.
• Edge from node 1 to 3, cost 50.

The answer for this test is 150, for this path 1->2->1->3. I am aware of Dijkstra algorithm. But I could not find anything on how to do this. I am sorry if this is and old topic but I when I googled it I could not find anything.

Update: I read this question. Which algorithm can I use to find the next to shortest path in a graph? My question is different from it because in this problem, I can use an edge twice. I am going from node 1 to 2 once, then coming back to 1. This using edge 1->2 twice.

Answer 1

I think this might work:

Maintain two arrays: shortest[i] and sec_shortest[i] which denote the shortest and the second shortest path lengths of vertex i respectively.

Now, all you need is to modify the method in the update part of Dijkstra's algorithm in a slightly different way:

for v in adj(u):
    if shortest[u] + cost(u, v) < shortest[v]:
        sec_shortest[v] = shortest[v]
        shortest[v] = shortest[u] + cost(u, v)
    else if shortest[u] + cost(u, v) < sec_shortest[v]:
            sec_shortest[v] = shortest[u] + cost(u, v)

In the end, sec_shortest[i] will contain the second shortest path length from the fixed source to vertex i.