Shortest Path Algorithm
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Shortest Path Algorithm

  1. #1
    Join Date
    Jan 2010
    Posts
    49

    Shortest Path Algorithm

    Hi

    Can anyone give C++ Implementation code to find shortest path between two Nodes.

    I am using Dijiktrax algorithm,,But for Graph which has 12,000 nodes its taking too much time to execute.

    Can we use any other algorithm to find shortest path.

    Please help me on this ..

    Thank You.

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Shortest Path Algorithm

    It seems,

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

    that the naive implementation is O(N*N) whereas a more involved version takes you down to O(N*logN). That's very much better.

    This could be what you're looking for,

    http://www.codeproject.com/KB/recipe...Algorithm.aspx
    Last edited by nuzzle; July 21st, 2011 at 01:36 AM.

  3. #3
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,012

    Re: Shortest Path Algorithm

    Quote Originally Posted by AbhiMFC View Post
    Can we use any other algorithm to find shortest path.
    If you just need to find one path, then an A* (A-star) algorithm should work better.
    However, in practice the implementation can also make a big difference in terms of performance. How do you represent the graph? Which data structures are you using for the other information?

    You might want to have a look at the Boost Graph Library.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  4. #4
    Join Date
    Jan 2010
    Posts
    49

    Re: Shortest Path Algorithm

    This is a Electrical Network,,Where we have Node(Poles) and Edges(Series elements like Transmission Line,Series reactor,etc),..

    So we have to find shortest path between given two nodes.

    We are Using CTypedPtrList class to store Nodes and Edges.

  5. #5
    Join Date
    Apr 1999
    Posts
    27,424

    Re: Shortest Path Algorithm

    Quote Originally Posted by AbhiMFC View Post
    This is a Electrical Network,,Where we have Node(Poles) and Edges(Series elements like Transmission Line,Series reactor,etc),..

    So we have to find shortest path between given two nodes.

    We are Using CTypedPtrList class to store Nodes and Edges.
    We don't discuss MFC here. That is for the Visual C++ forum.

    Unless you want to reinvent the wheel, use the boost graph library:

    http://www.boost.org/
    http://www.boost.org/doc/libs/1_47_0..._contents.html
    http://www.boost.org/doc/libs/1_47_0...ar_search.html

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; July 21st, 2011 at 05:10 AM.

  6. #6
    Join Date
    Jan 2010
    Posts
    49

    Re: Shortest Path Algorithm

    Do i need to post new post again in Visual C++ section or can i transfer entire discussion thread to VC++ section.

  7. #7
    Join Date
    Apr 1999
    Posts
    27,424

    Re: Shortest Path Algorithm

    Quote Originally Posted by AbhiMFC View Post
    Do i need to post new post again in Visual C++ section or can i transfer entire discussion thread to VC++ section.
    Finding the shortest path is not really a C++ topic, whether it is Visual C++ or not -- it is an algorithm topic and there is an algorithm forum here.

    If your discussion is about finding the shortest path and you want C++ code to do so, then the links I have shown you are to the boost C++ libraries that have already implemented this.

    Regards,

    Paul McKenzie

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center