Results 1 to 5 of 5
  1. #1
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

    Question 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. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Claymz View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

    Default

    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. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Claymz View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Claymz is offline Member
    Join Date
    Apr 2011
    Posts
    25
    Rep Power
    0

    Default

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

Similar Threads

  1. Replies: 3
    Last Post: 10-12-2010, 04:21 PM
  2. "Best" implementation of math operator methods?
    By rgrant222 in forum New To Java
    Replies: 2
    Last Post: 09-01-2010, 07:47 AM
  3. Replies: 1
    Last Post: 01-21-2010, 09:20 AM
  4. Replies: 2
    Last Post: 01-24-2009, 06:56 PM
  5. Replies: 1
    Last Post: 10-20-2008, 07:35 AM

Tags for this Thread

Posting Permissions

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