468,134 Members | 1,181 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,134 developers. It's quick & easy.

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

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
Jul 28 '10 #1
3 6972
jkmyoung
2,057 Expert 2GB
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.
Jul 29 '10 #2
@jkmyoung
Hi jkmyoung,

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

Thanks so much.
Jul 30 '10 #3
jkmyoung
2,057 Expert 2GB
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
Aug 4 '10 #4

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

reply views Thread by Frederick Noronha \(FN\) | last post: by
21 posts views Thread by Jaspreet | last post: by
16 posts views Thread by liking C lang. | last post: by
3 posts views Thread by Grizlyk | last post: by
1 post views Thread by =?Utf-8?B?Qm9iQWNoZ2lsbA==?= | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.