CODEWITHSUNDEEP
calgorithmdata-structures
Tiago Costa
Tiago Costa

Reputation: 4251

How to store adjacent nodes for Dijkstra algorithm?

Most articles about Dijkstra algorithm only focus on which data structure should be used to perform the "relaxing" of nodes.

I'm going to use a min-heap which runs on O(m log(n)) I believe.

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

How will that change the running time of the algorithm?

Upvotes: 4

Views: 678

Answers (2)

Bernhard Barker
Bernhard Barker

Reputation: 55609

With Dijkstra's algorithm you just loop through the list of neighbours of a node once, so a simple array or linked list storing the adjacent nodes (or simply their indices in a global list) at each node (as in an adjacency list) would be sufficient.

How will that change the running time of the algorithm? - in comparison to what? I'm pretty sure the algorithm complexity assumes an adjacency list implementation. The running time is O(edges + vertices * log(vertices)).

Upvotes: 0

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

For the algorithm itself, I think you should aim for compact representation of the graph. If it has a lot of links per node, a matrix may be best, but usually an adjacency list will take less space, and therefore less cache misses.

It may be worth looking at how you are building the graph, and any other operations you do on it.

Upvotes: 1

Related Questions