Finding K Shortest Paths Between Source and Destination
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

Thread: Finding K Shortest Paths Between Source and Destination

  1. #1
    Join Date
    Sep 2008
    Posts
    5

    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.

  2. #2
    Join Date
    Sep 2008
    Posts
    5

    Re: Finding K Shortest Paths Between Source and Destination

    is this so tough...so many views but no replies...pls guys someone help me...

  3. #3
    Join Date
    Jul 2008
    Location
    Be'er Sheva, Israel
    Posts
    69

    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?

  4. #4
    Join Date
    Feb 2008
    Posts
    966

    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.

  5. #5
    Join Date
    Sep 2008
    Posts
    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....

  6. #6
    Join Date
    Feb 2008
    Posts
    966

    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

  7. #7
    Join Date
    Sep 2008
    Posts
    5

    Re: Finding K Shortest Paths Between Source and Destination

    Thanks a lot to program this...

  8. #8
    Join Date
    Sep 2008
    Posts
    5

    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...

  9. #9
    Join Date
    Oct 2005
    Posts
    10

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center