• C

k-shortest path implementation with C language

Hi.
By using Dijkskta algorimth i have implemented an application for find the 1st shortest path of an optical network. Unfortunately, this is not enough. It is necessary to calculate the 2st & 3rd shortest path, using the same algorithm or something else, always by using language C. Do you have any idea how to do it??

www.cs.bham.ac.uk/~mhe/foundations2/node113.html - 16k -
(my code is similar to  the code of the above link)
tsakyrAsked:
Who is Participating?
 
sunnycoderConnect With a Mentor Commented:
Btw, you can use your existing algo too ...

Find the shortest path
second_shortest = HIGH_VALUE
for all edges in shortest path
     remove the edge
     current = find the shortest path
     second_shortest = min (second_shortest, current)
     put back edge
end for

If you iterate over this pseudocode k times - removing the edge for shortest path each time, you would have k shortest paths.
0
 
sunnycoderCommented:
http://www.dis.uniroma1.it/~challenge9/papers/santos.pdf

Implementation of K-shortest Path Dijkstra Algorithm used in All-optical Data Communication Networks
http://www.u.arizona.edu/~saurabh/SIE/kDijkstra546.pdf
0
 
tsakyrAuthor Commented:
Realy, thanks a lot.
0
 
sunnycoderCommented:
Glad to help :)

Was wondering why you chose a B grade. Pls refer to grading guidelines here
http://www.experts-exchange.com/help.jsp#hi403
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.