CODEWITHSUNDEEP
algorithmgraph-algorithmdijkstra
troopers97
troopers97

Reputation: 91

What is the space complexity of Dijkstra Algorithm?

The time complexity for Dijkstra Algorithm using an array is O(V^2) and if priority queue is implemented, we can further improve the complexity to O(E log V). But what about its space complexity? Is it O(V) in both cases?

Upvotes: 6

Views: 18517

Answers (3)

Yude Wei
Yude Wei

Reputation: 46

Update:

It should be o(V).

See https://cs.au.dk/~gerth/papers/fun22.pdf

In the improved version, I think the space complexity should be O(V^2) in the worst case suppose every node is connected with each other, because we may design a graph that has every node which is not relaxed to minimum as a neighbor to the current node go into the heap again and again and we can do it for V times of loops. That is (V-2) + (V-3) + ... + 2 + 1, which is O(V^2). I am not sure.

EXAMPLE (undirected, directed is also good):

adjacency list:
0: {0, 0}, {1, 64}, {2, 128}, {3, 256}
1: {0, 64}, {1, 0}, {2, 32}, {3, 16}
2: {0, 128}, {1, 32}, {2, 0}, {3, 8}
3: {0, 256}, {1, 16}, {2, 8}, {3, 0}

0 is the source

Init:

dis: 0 -1 -1 -1
heap: {0, 0}

EXECUTION:

dis: [0] 64 128 256
heap: {64, 1}, {128, 2}, {256, 3} size: +3 -1

dis: [0] [64] 96 80
heap: {80, 3}, {96, 2}, {128, 2}, {256, 3} size: +2 -1

dis: [0] [64] 88 [80]
heap: {88, 2}, {96, 2}, {128, 2}, {256, 3} size: +1 -1

dis: [0] [64] [88] [80]
heap: {96, 2}, {128, 2}, {256, 3} size: +0 -1

Upvotes: 1

Manmay Barot
Manmay Barot

Reputation: 185

Time and Space for Dijkstra Algorithm:

  • Time: O((|V| + |E|) log V)
  • Space: O(|V| + |E|)

However, (E >= V - 1) so |V| + |E| ==> |E|. But usually we use both V and E

Upvotes: 4

PiJei
PiJei

Reputation: 604

If you implement Disjkstra's shortest path algorithm using a MinHeap (aka priority queue), which in turn uses an array for storing the heap , and also if you use an array to store the values of the shortest distance for every node in the graph, your space complexity will be O(V) + O(V) = O(2V) =~ O(V)

Upvotes: 2

Related Questions