# Thread: implementation of "shortestPath"

1. Member
Join Date
Apr 2011
Posts
25
Rep Power
0

## implementation of "shortestPath"

Hi,

i would like to implement my own class, which does the same as the "shortestPath" method of "WeightedGraph" class, that is, enumerate the nodes in a shortest path between two given nodes, where shortest path means the smallest number of edges, which connect them.

Im going to take Dijkstra's princip, and check every edge of a each vertex, and save verticies which represent the shortest path between the two, but doing so, in worst case i have to go through every vertex and every edge. Is there any less (memory) consuming way to do this, or you need to examine complete graph (vertecies and edges are inputed randomly, no order is applied)? And if it is, what are the neccessery terms?

Ty!
Last edited by Claymz; 05-25-2011 at 03:06 PM.

2. Originally Posted by Claymz
Hi,

i would like to implement my own class, which does the same as the "shortestPath" method of "WeightedGraph" class, that is, enumerate the nodes in a shortest path between two given nodes, where shortest path means the smallest number of edges, which connect them.

Im going to take Dijkstra's princip, and check every edge of a each vertex, and save verticies which represent the shortest path between the two, but doing so, i have to go through every vertex and every edge. Is there any less (memory) consuming way to do this, or you need to examine complete graph (vertecies and edges are inputed randomly, no order is applied)? And if it is, what are the neccessery terms?
If your definition of the shortest path is "the smallest number of edges which connect them" then all edge weights have to be equal, say 1. The Dijkstra algorithm is as cheap as they come, i.e. keep on labeling the front of a heap containing the partial shortest paths until you've reached the destination vertex. There is not much to make it cheaper.

kind regards,

Jos

3. Member
Join Date
Apr 2011
Posts
25
Rep Power
0
argh, im trying so hard i cant even go to sleep... Everything i try i get lost because of the vast code. Can somebody give me a hint or something that could help me do this in an easy, efficient way? Im storing verticies in a list of one way pointers, just to be exact, and each vertex has a list of its edges stored the same way.

Most problems occur keeping a track of all current (usable) paths.
Last edited by Claymz; 05-26-2011 at 05:19 AM.

4. Originally Posted by Claymz
argh, im trying so hard i cant even go to sleep... Everything i try i get lost because of the vast code. Can somebody give me a hint or something that could help me do this in an easy, efficient way? Im storing verticies in a list of one way pointers, just to be exact, and each vertex has a list of its edges stored the same way.

Most problems occur keeping a track of all current (usable) paths.
Have you implemented a ´heap´? The heap contains the vertexes ordered by the cost of the route ending in that vertex point. The vertex should also point to a previous vertex in the route that is consequently also present in the heap. An ordered set is ideal for this purpose.

kind regards,

Jos

5. Member
Join Date
Apr 2011
Posts
25
Rep Power
0
With a source code help, i used BFS algorithm, and implemented graph using Map to make it work! Ty for your response! :)

#### Posting Permissions

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