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!

Quote:

---

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

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.

Quote:

---

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

With a source code help, i used BFS algorithm, and implemented graph using Map to make it work! Ty for your response! :)