Shortest Path Algorithm

[AbhiMFC]

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.

[nuzzle]

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

[D_Drmmr]

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.

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

[Paul McKenzie]

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

[AbhiMFC]

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

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

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