How to get the second shortest path or k-shortest path

[Nguyen2010]

Hello All,

I very need the code of the second shortest path or k-shortest paths that paths are separate(only same as source and destination) and find them almost parallel(not find the shortest path, remove it then find the second path...).

Could you please send me soon.

Thank you very much!
Nguyen

[jkmyoung]

I recommend an altered Dijkstra's algorithm. In this, keep two sets of values, one the best, and the other the second best.

You can similarly extend to k-shortest paths, although this will require much more memory and exponentially more processing time.

[Nguyen2010]

I recommend an altered Dijkstra's algorithm. In this, keep two sets of values, one the best, and the other the second best.

You can similarly extend to k-shortest paths, although this will require much more memory and exponentially more processing time.

Hi jkmyoung,

Could you tell me how to choose the second best set?

Thanks so much.

[jkmyoung]

Doing this with the example on wikipedia on the right:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

start with distance values to each of the nodes as
d2: inf, inf
d3: inf, inf
d4: inf, inf
d5: inf, inf
d6: inf, inf

We have 6 nodes with following edge weights from 1:
(12) - 7, (13) - 9, (16) - 14
So we set
d2 := 7, inf
d3 := 9, inf
d6 := 14, inf

Next round:
(23) = 10, (24) = 15. Here is where it gets a little tricky. Do the incoming edges to 2 first, to find the second edge.
d2:= 7, 19 (19 is 9 + edge of 10)
then set the other vertices:
d3:= 9, 17
d4:= 22, 34

Total:
*d2: 7, 19
d3: 9, 17
d4: 22, 34
d5: inf, inf
d6: 14, inf

Next round:36 = 2, 34 = 11
d3:= 9, 16
There might be some more backtracking, so we double check, 16 + (32) = 16 + 10 = 26 > 19. No more back tracking needed
d6:= 11, 14 (quick back check of edges from 6 reveals no updates needed)
d4, comparing, 20, 27 with 22, 34, we get
d4:= 20, 22

Total:
*d2: 7, 19
*d3: 9, 16
d4: 20, 22
d5: inf, inf
d6: 11, 14

Next is 6: (65) = 9
*d2: 7, 19
*d3: 9, 16
d4: 20, 22
d5: 20, 23
*d6: 11, 14

Finally, we have 4: (45) = 6
d4 + 45 = 26, 28. comparing to 20, 23 nothing changes.

End result:
*d2: 7, 19
*d3: 9, 16
*d4: 20, 22
*d5: 20, 23
*d6: 11, 14

Finding the path back:
You could also store where the last 2 edges came from, to do this quickly. However, it requires more space.
the 2nd furthest path to d5 is 23.

23 - (54) = 17, doesn't match
23 - (56) = 14. Match
14 - (61) = 0 Match (since node 1 implicitly contains values (0, inf).
The second furthest path to node 5 from 1 is 1 - 6 - 5