Printable View
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.
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
If you just need to find one path, then an A* (A-star) algorithm should work better.Quote:
Originally Posted by AbhiMFC
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.
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.Quote:
Originally Posted by AbhiMFC
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
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.Quote:
Originally Posted by AbhiMFC
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