-
July 21st, 2011, 01:03 AM
#1
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.
-
July 21st, 2011, 01:25 AM
#2
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.
-
July 21st, 2011, 04:15 AM
#3
Re: Shortest Path Algorithm
Originally Posted by AbhiMFC
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
-
July 21st, 2011, 04:54 AM
#4
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.
-
July 21st, 2011, 05:05 AM
#5
Re: Shortest Path Algorithm
Originally Posted by AbhiMFC
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.
-
July 21st, 2011, 05:16 AM
#6
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.
-
July 21st, 2011, 05:23 AM
#7
Re: Shortest Path Algorithm
Originally Posted by AbhiMFC
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|