Help with impletementing dijkstra's Algorithm

[imhiya]

I have two files; one with places then the distance between them.

Example:
Moffat Carlisle 65
Doncaster Hull 76
Northampton Birmingham 90
Leicester Lincoln 82
Sheffield Birmingham 122


I was wanting to use dijkstra's method, but i seem to have a problem because looking pseudo codes to understand it they all ask for a node, then all the connecting nodes. The problem is that the file is unordered so it will keep changing nodes. I thought i could search if it's already in the array/vector. If not then add it, but the problem with this is i don't know how many connecting nodes there is, so i would have to include a expanding varible.

The second file, contains a source city and dest city, which i have to work out the shortest path.

hope you can help!

[simeonz]

Given the circumstances, what I would do is to put the data in vector, to sort the vector with the STL sort algorithm, and to answer the neighbor queries for a node using lower_bound and upper_bound STL algorithms.

This is binary search once per node for every extract-min from the priority queue and once per edge for every attempt to decrease-key, assuming you use sorted vector for the path records too. Searching will require O(log E) steps per query, so overall, the asymptotic performance of the algorithm will be O(E log(E) + V log(E)) = O((E + V) log(E)) = O(E log(E)). The initial sorting will require O(E log(E)), and therefore you are stuck with this performance from the pre-processing step.

Now, if you needed to perform several runs with different inputs, you could transform the input data into adjacency lists, but if I understand correctly, this is not your case. Also, you can use hash-map to improve the expected asymptotic performance, since you need unordered associative search, although you may encounter worse performance with very small probability. (Using sorted vector as I suggest makes more sense when you need ordered associative container.)

As a side note, you may need to implement the priority queue yourself, because the std one does not support decrease-key.

Regards

EDIT: Actually, searching for the path record of a node will require O(log(V)) steps, but for (non-multi) graph it is the same in asymptotic formulas, because V + 1 <= E <= V * (V - 1), consequently O(log(E)) = O(log(V)).