Космическая сложность Дейкстра ⇐ Python

[Anonymous]

Я работал над некоторыми вопросами LeetCode для алгоритма Dijkstra, и я не совсем понимаю ее сложность. Я посмотрел онлайн, но нашел различные ответы, а некоторые были довольно сложными, поэтому я хотел знать, правильно ли я понял это. < /P>

Код: Выделить всё

# 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))

Поскольку я использую набор визита и очередь приоритетов , чтобы отслеживать узлы, будет ли простой сложности простой просто o (v), где v - это количество вершин на графике? И если бы мне пришлось сгенерировать список смежности в Python, используя DICT , у которого была бы пространственная сложность O (e), где e - количество краев?

Подробнее здесь: https://stackoverflow.com/questions/788 ... f-dijkstra