Space Complexity of Dijkstra

Question

I was working on some Leetcode questions for Dijkstra's algorithm and I do not quite understand the space complexity of it. I looked online but I found various answers and some were rather complicated so I wanted to know if I understood it correctly.

# initialize maxheap
maxHeap = [(-1, start_node)]
heapq.heapify(maxHeap)

# dijkstras algorithm
visit = set()
res = 0
while maxHeap:
    prob1,cur = heapq.heappop(maxHeap)
    visit.add(cur)

    # update result
    if cur == end_node: 
        res = max(res, -1 * prob1)

    # add the neighbors to the priority queue
    for nei,prob2 in adj_list[cur]:
        if nei not in visit: heapq.heappush(maxHeap, (prob1 * prob2, nei))

Since I use a visit set and a priority queue to keep track of the nodes would the space complexity just simply be O(V) where V is the number of vertices in the graph? And if I had to generate an adjacency list in Python using a dict would that have a space complexity of O(E) where E is the number of edges?

Answer 1

Since I use a visit set and a priority queue to keep track of the nodes would the space complexity just simply be O(V) where V is the number of vertices in the graph?

For what concerns the set: yes. In the worst case, the target is the last node that could be visited, and then set will in the end have an entry for every node that is reachable from the start node, so O(𝑉') where 𝑉' is the number of nodes in the connected component where you start the search. That is O(𝑉) when the graph is connected.

For what concerns the priority queue: this is not guaranteed. As you only mark nodes as visited when you pull them from the queue, you can potentially have multiple occurrences of the same node in the queue at a given moment. The limit on the number of heappush calls is given by the number of edges. So we have a worst case space complexity of O(𝐸) for the priority queue.

And if I had to generate an adjacency list in Python using a dict would that have a space complexity of O(E) where E is the number of edges?

That depends on whether you create dict-keys for nodes that have no outgoing edges (with empty lists as values). If so, then it is Θ(𝑉+𝐸). If you omit keys that would represent such nodes (without outgoing edges), then it is indeed Θ(𝐸), but then your program needs to have a check whether adj_list[cur] exists or not.

Other remarks

• You don't need to call heapify when your list has only one element. A list with one element is already a valid heap.

• When you pop a node from the queue, you should verify whether it was already visited. This could happen when a node was pushed on the queue multiple times (as it was encountered via different paths), before the first occurrence was popped from it. In that case you'll mark it as visited as the first occurrence is popped from the queue, but then it might eventually get popped a second time: and then you should not process it.

• When you find the target node, and have res, you should exit the loop

• Instead of assigning to res, it would be good practice to wrap this code in a function and return that value.

So:

def dijkstra(adj, start_node, end_node):
    # initialize maxheap
    maxHeap = [(-1, start_node)]

    # dijkstra's algorithm
    visit = set()
    while maxHeap:
        prob1, cur = heapq.heappop(maxHeap)
        if cur in visit:
            continue
        visit.add(cur)

        # update result
        if cur == end_node: 
            return max(res, -1 * prob1)

        # add the neighbors to the priority queue
        for nei,prob2 in adj_list[cur]:
            if nei not in visit: 
                heapq.heappush(maxHeap, (prob1 * prob2, nei))

    return 0  # end_node not reachable