# What is the space complexity of Dijkstra Algorithm?

As per my understanding. The space complexity will be O(V). An array of V nodes will be created which in turn be used to create the Min heap.

But this link is stating that It is O(V^2)? I don't understand how it can be O(V^2)?

I have search the same topic in the Book entitled Introduction_to_Algorithms by Thomas H. Cormen but still not able to find the answer. I Don't understand what I am missing.

I can't think of a way of implementing Dijkstra to use $$|V|^2$$ space, but I would note two things.
1. $$O(\cdot)$$ only gives an upper bound. Even if the implementation actually uses space $$O(|V|)$$, it's not wrong to say that it uses $$O(|V|^2)$$ or even $$O(2^{|V|})$$, just as it's not wrong to say that I earn less than a billion dollars a year. However, it would be unusual to say $$O(|V|^2)$$ if it was easy to prove the stronger bound of $$O(|V|)$$ (I also earn less than a million dollars a year), and it is easy to prove $$O(|V|)$$ for most implementations of Dijkstra.
2. The page quotes the running time as $$O(s|E|\log|E|+V)$$, where $$s$$ is the number of sources being considered. It's easy to imagine space usage of $$O(s|V|)$$ so maybe they wrote $$O(|V|^2)$$ since $$s\leq|V|$$. But that would also be strange, given that the quoted running time shows they're not afraid to use $$s$$.