Shortest Path Algorithm
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

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

Thank You.

2. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Shortest Path Algorithm

It seems,

http://en.wikipedia.org/wiki/Dijkstra&#37;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. ## 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.

4. Member
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. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

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

6. Member
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. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## 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
•