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? Continue reading...
