If you implement Dijkstra's algorithm using a heap to determine the next node to visit, what is the space complexity? The problem is that you cannot delete nodes from the heap, so duplicate entries will appear.
This source says O(V) space: https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/ however that does not seem correct to me.
The source you quote is wrong. We can imagine a complete, weighted graph, where the priority queue would get all non-processed nodes added to it in each iteration of the main loop. In the worst case, we would pull in each iteration 𝑖 of the main loop a node that was not processed before, leaving all its duplicates on the queue. The size of the queue (𝑇) would grow like this:
This resolves to:
𝑇𝑖 = 1 + (𝑖−1)(𝑉−1) − 𝑖(𝑖−1)/2
When the last non-processed node being pulled from the queue happens to be the target (worst case in terms of space complexity), we have at that time the following queue size:
𝑇𝑉 = 1 + (𝑉−1)(𝑉−1) − 𝑉(𝑉−1)/2 = 1 + (𝑉−1)(𝑉−1−𝑉/2)
...which is O(𝑉²)