How to store neighboring nodes for Dijkstra's algorithm?

Question

Most articles on Dijkstra’s algorithm focus only on what data structure should be used to perform the “relaxation” of nodes.

I am going to use a mini-heap that works on O(m log(n)) I believe.

My real question is, what data structure should I use to store the neighboring nodes of each node? I am thinking about using an adjacency list because I can find all the neighboring nodes on u in O(deg(u)) , is this the fastest method?

How will this change the running time of the algorithm?

Answer 1

With the Dijkstra algorithm, you simply look at the list of neighbors of a node once, so a simple array or linked list that stores adjacent nodes (or just their indices in the global list) in each node (as in an adjacency list).

How will that change the running time of the algorithm? - compared to what? I am sure that the complexity of the algorithm involves the implementation of an adjacency list. Run time O(edges + vertices * log(vertices)) .

Answer 2

For the algorithm itself, I think you should strive for a compact graph representation. If it has a lot of node references, the matrix might be better, but usually an adjacency list takes up less space and therefore less cache misses.

It might be worth a look at how you build the chart, and any other operations that you do on it.