Results 1 to 5 of 5
Thread: implementation of "shortestPath"
 05252011, 04:01 PM #1Member
 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; 05252011 at 04:06 PM.
 05252011, 04:09 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,771
 Blog Entries
 7
 Rep Power
 21
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,
Joscenosillicaphobia: the fear for an empty beer glass
 05262011, 06:15 AM #3Member
 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; 05262011 at 06:19 AM.
 05262011, 09:31 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,771
 Blog Entries
 7
 Rep Power
 21
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,
Joscenosillicaphobia: the fear for an empty beer glass
 05302011, 08:53 PM #5Member
 Join Date
 Apr 2011
 Posts
 25
 Rep Power
 0
Similar Threads

connection = DriverManager.getConnection(DATABASE_URL,'"+userid +"','"+password+"');
By renu in forum New To JavaReplies: 3Last Post: 10122010, 05:21 PM 
"Best" implementation of math operator methods?
By rgrant222 in forum New To JavaReplies: 2Last Post: 09012010, 08:47 AM 
How to change my form design from "metal" to "nimbus" in Netbeans 6.7.1?
By mlibot in forum New To JavaReplies: 1Last Post: 01212010, 10:20 AM 
MoneyOut.println("It took you (whats wrong?>",year,"<WW?) years to repay the loan")
By soc86 in forum New To JavaReplies: 2Last Post: 01242009, 07:56 PM 
the dollar sign "$", prints like any other normal char in java like "a" or "*" ?
By lse123 in forum New To JavaReplies: 1Last Post: 10202008, 08:35 AM
Bookmarks