Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Help program Dijksttra's algorithim to find single source sourtest path?

  1. #1
    Junior Member
    Join Date
    Mar 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Help program Dijksttra's algorithim to find single source sourtest path?

    I am having a hard time getting started with this program. It can be written in any language (but I prefer java or maybe C).

    I have been given a graphs in the form of an adjacency list in a text file. My goal is simply to print the distance of the single source shortest path in the graph (that is, starting at node 0 and visiting every node with a minimum weight, and then print the weight). Some of the lists are huge (over 100,000 nodes) but here is the format of the list:

    n=1000 m=8544

    0
    25 244
    108 275
    140 273

    1
    24 187
    43 182

    This is just the first few lines of the file, but the format is:

    n= number of nodes
    m= number of edges

    then there is a blank line separating each node. On the next line, the node is named (only node 0 and 1 are shown in this example). After the name of the node, each line shows two numbers. The first number is the neighbor nodes name, and the second number is the weight of the edge. So in the example I gave, there are 1000 nodes with 8544 edges. The node named "0" is neighbors with "25" and the weight is 244. Node "0" is also neighbors with "108" and its weight is 275. Node "1" is neighbors with "24" with weight 187, etc...

    THIS GRAPH IS UNDIRECTED, BUT THE EDGES ARE ONLY MENTIONED ONCE IN THE LIST! (you can obviously travel from 0 to 25, but you can also travel from 25 to 0 even though 0 is NOT listed in 25's adjacency list, it is just to be assumed that all edges are traversable in both directions).

    I know how to read in files and parse them, and I know how the algorithm works (if I had a picture of the graph in front of me). I am just having a hard time connecting this adjacency list to the algorithm to the actual code. How would you do this and what data structures would you use? (I am not asking for code, unless you really want to write some. I just need something to spark my brain).


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Help program Dijksttra's algorithim to find single source sourtest path?

    One of the simplest ways to represent a graph data structure is to use a list of vertices, and then under each vertex, have a list of nodes that vertex is directly connected to and the weight of the path. While your file may not have a path represented more than once, it's an extremely useful and good optimization to have every path leading from a vertex listed for that vertex.

    So, a sample graph might look something like this (note that this graph could have one-way edges, but it's possible to create a graph using this exact same technique with only two-way edges)

    vertex 1: [vertex 2, 1], [vertex 3, 3]
    vertex 2: [vertex 1, 1], [vertex 4, 1]
    vertex 3: [vertex 1, 3]
    vertex 4: [vertex 2, 1]

    Once you have your graph represented, you can run Dijkstra's algorithm by finding the starting node first, then propagating out according to the algorithm (having a boolean "wasVisited" field inside each vertex would be very useful).

  3. #3
    Junior Member
    Join Date
    Mar 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help program Dijksttra's algorithim to find single source sourtest path?

    Ok, so it looks like I could create an array for every node. Maybe use the [0] element for the Boolean was visited, and use the rest of the elements in the array to hold neighbors and their corresponding weights?

    And because the returning edges are not specifically given to me, but are assumed to exist, I am going to have to have to edit two arrays every time I scan a new line.

    Once this is all done, I start at array 0 and find the smallest weight neighbor. I mark array 0 as visited (never compare this array to anything again), then add the weight to the min_weight variable, and continue from whatever node I ended up at from node 0. Once all arrays have been marked as visited, print the min_weight.

    Does this sound reasonable? Is it going to be a problem having literally tens of thousands of arrays created at once? The program is supposed to complete in less than 10 seconds (when there is 100,000 nodes). Will this be efficient enough?

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Help program Dijksttra's algorithim to find single source sourtest path?

    If you're running on a modern computer (and as long as you don't have any glaring inefficiencies), I don't see why you wouldn't finish under a few seconds seconds.

    Why use the 0'th element for a boolean was visited? Technically it should work, but that's taking away from the OO nature of Java. Create a node class which contains a boolean isVisited and a list of nodes that node is connected to. Personally, I wouldn't recommend using an array because it will make building your graph a big pain, try using a built-in list type such as the ArrayList or LinkedList, these will make building your graph much easier (actually, technically you could use any collection which allows you to iterate through all the elements).

    In Djikstra's algorithm, you actually need the min distance from the start node to every other node. I kind of forgot about that earlier, so that would just be another field inside your node class. When you've visited every node, you can just pick a target node and print out the min distance field of that node.

    edit: oh, one last thing (hopefully) is that you need to initialize the initial min distance from the start node to be infinity (or something really large), otherwise there's a chance you'll get a bogus result.
    Last edited by helloworld922; March 17th, 2011 at 12:28 PM.

Similar Threads

  1. CHALLENGE - find the shortest path
    By ice in forum Algorithms & Recursion
    Replies: 13
    Last Post: January 20th, 2011, 12:30 PM
  2. locating the path to a jar file within a program
    By nemo in forum What's Wrong With My Code?
    Replies: 7
    Last Post: January 2nd, 2011, 05:41 PM
  3. client server program on a single machine
    By subhopam in forum Java Networking
    Replies: 1
    Last Post: December 16th, 2009, 02:02 PM
  4. how to get full path name from realtive path
    By priyanka3006 in forum File I/O & Other I/O Streams
    Replies: 8
    Last Post: August 10th, 2009, 05:28 AM
  5. [SOLVED] How to a set java class path?
    By captjade in forum Java Theory & Questions
    Replies: 1
    Last Post: March 10th, 2009, 07:40 AM