What is the space complexity of Dijkstra Algorithm?

Question

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?

Solution

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

Comments

[Ivan Smirnov]

Did you analyzing it yourself? Try calculating what values the algorithm should store, show us your approach.