
September 6th, 2008, 04:23 PM
#1
Finding K Shortest Paths Between Source and Destination
Hi..
I am trying to write a code in C++ for K shortest paths between source and destination nodes. Using the the Dijkstra's algorithm i am able to get the first shortest path and i am not able to proceed further to get the rest of the shortest paths.
I even tried to find all the paths in the graph and then sort the cost of each path to my need. But for that i need to find all the paths from source to destination but i am unable to find.
I need this assignment to be done quickly. If anybody can help me with the code, I would so helpful to me.
Thanks in advance.

September 7th, 2008, 12:33 PM
#2
Re: Finding K Shortest Paths Between Source and Destination
is this so tough...so many views but no replies...pls guys someone help me...

September 7th, 2008, 07:28 PM
#3
Re: Finding K Shortest Paths Between Source and Destination
Hi Arun,
Please clarify, as shortest path is defined a path that has minimum weight between source vertex s and target vertex t, what is the meaning of K shortest paths, from single source? a predefined source to predefined sink? these things are not clear from your description.
How often do you look at a man's shoes?

September 8th, 2008, 12:22 PM
#4
Re: Finding K Shortest Paths Between Source and Destination
The simple solution is to modify your search so that it does not terminate when it finds the shortest path, but actually stores it in an array (data structure). Have the algorithm continue until it has reached the desired number of shortest paths or it has reached the end of the tree.

September 8th, 2008, 07:33 PM
#5
Re: Finding K Shortest Paths Between Source and Destination
In a directed graph there are many paths between a single source and single destination...using a shortest path algorithm like djikstra's we get only the first shortest path...
Wat i want is the next shortest path and further on...till all the paths between the source and destination are got in a descending order of their weights...
here K represents the number of paths we want....
like if K = 5
then then all the first shortest path should be got....

September 9th, 2008, 04:22 PM
#6
Re: Finding K Shortest Paths Between Source and Destination
Sounds like you can't use Dijkstra's algorithm then does it not? I see loads of research papers on finding the Kth number of shortest paths out there. Why you couldn't find any is beyond me. I've done your Google research for you because I was interested in seeing such an algorithm myself, and decided to post it here so anybody interested and too lazy to use Google can see also...
Why don't you go check out this article on A*Prune.
Or if you cannot understand that one, try this one

September 9th, 2008, 07:39 PM
#7
Re: Finding K Shortest Paths Between Source and Destination
Thanks a lot to program this...

September 13th, 2008, 03:17 PM
#8
Re: Finding K Shortest Paths Between Source and Destination
I tried implementing the A* prune pseudo code in C ++....but i am unable to proceed....I am finding a big problem in doing the minimum admissible path part...also i have just now started reading C++...If anybody can help me with the entire code den its so helpful for me...
thanks in advance...

November 2nd, 2008, 01:49 AM
#9
Re: Finding K Shortest Paths Between Source and Destination
hi arun
i need to solve almost the same problem... did u come up with a code that allows u to find the K shortest paths?
here is my thread: http://www.codeguru.com/forum/showth...ighlight=paths
Thank you
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
OnDemand Webinars (sponsored)
