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

Printable View

• March 16th, 2011, 09:53 PM
mattpd
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).
• March 17th, 2011, 03:28 AM
helloworld922
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).
• March 17th, 2011, 10:58 AM
mattpd
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?
• March 17th, 2011, 11:09 AM
helloworld922
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.