Thread: 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).

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?