Does time complexity of dijkstra's algorithm for shortest path depends on data structure used?

2
votes

One way to store the graph is to implement nodes as structures, like

struct node {
int vertex; node* next; 
};

where vertex stores the vertex number and next contains link to the other node.

Another way I can think of is to implement it as vectors, like

vector<vector< pair<int,int> > G;

Now, while applying Dijkstra's algorithm for shortest path, we need to build priority queue and other required data structures and so as in case 2 (vector implementation). Will there be any difference in complexity in above two different methods of applying graph? Which one is preferable?

EDIT: In first case, every node is associated with a linked list of nodes which are directly accessible from the given node. In second case, G.size() is the number of vertices in our graph G[i].size() is the number of vertices directly reachable from vertex with index i G[i][j].first is the index of j-th vertex reachable from vertex i G[i][j].second is the length of the edge heading from vertex i to vertex G[i][j].first

1
c++data-structuresgraph-algorithmdijkstra
In a sense it does, when the original complexity analysis assumes something being O(1) (e.g. access into an array) and you replace that by something that has a worse complexity, then that will affect the overall complexity (in most cases). - PlasmaHH
For the first representation, am I correct in saying you're talking about a linked-list per vertex (which can, without much loss of generality, be simplified to vector<list<int> >)? For the second, will every pair in G[x] contain x (otherwise you'll need to elaborate)? - Bernhard Barker
@Dukeling Yes, you are right. I mean that only. - UserCPP

1 Answers

1
votes

Both are adjacency list representations. If implemented correctly, that would be expected to result in the same time complexity. You'd get a different time complexity if you use an adjacency matrix representation.

In more detail - this comes down to the difference between an array (vector) and a linked-list. When all you're doing is iterating through the entire collection (i.e. the neighbours of a vertex), as you do in Dijkstra's algorithm, this takes linear time (O(n)) regardless of whether you're using an array or linked-list.

The resulting complexity for running Dijkstra's algorithm, as noted on Wikipedia, would be
O(|E| log |V|) with a binary heap in either case.