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

Отвечать:

1. Ваш набор ни в коем случае не может доминировать в приоритетной очереди.
2. Если список смежности имеет значение на вашей стороне (т. е. вы получаете необработанные данные, скажем, описанные на человеческом языке и вам нужно самостоятельно построить список смежности), то он может доминировать, а может и не доминировать, в зависимости от реализации приоритета. очередь и свойство графа.

Объяснение:

Heapq Python использует список в качестве базовой структуры данных, вы уже купили его, как и maxHeap = [(-1, start_node)]. Таким образом, его пространственная сложность равна Θ(n), где n — количество элементов в списке.

Какой тогда номер? это зависит от ребер и вершин в графе, краткий ответ: если вершины доминируют над ребрами, то O(V), если наоборот, то O(E), но для общего случая мы можем обозначить это как O(V+E) ). это O(V+E) вместо O(V), учитывая асимптотическое соотношение между V и E, его можно дополнительно переписать как O(V^2).

Почему? поскольку вы использовали heapq Python, он не обеспечивает операцию increamentKey/decreamentKey, при обработке графа вам может потребоваться включить много узлов, которые вы еще не можете определить, что с ним делать.

Таким образом, набор никогда не может доминировать, поскольку он равен O(V), в лучшем случае, когда вершины доминируют над ребрами, он может связываться только с heapq. Однако для списка смежности, если вы использовали версию приоритетной очереди DIY, где разрешена операция decrementKey, следовательно, вы получаете сложность пространства O (V), тогда, если E доминирует над V, вы получаете O (E) списка смежности вместо O очереди приоритетов. (В).

Поскольку я использую набор посещений и очередь приоритетов для отслеживания узлов, будет ли сложность пространства просто равна O (V), где V — количество вершин в графе?

Что касается комплекта: да. В худшем случае целью является последний узел, который можно посетить, и тогда set в конце концов будет иметь запись для каждого узла, достижимого из начального узла, поэтому O(𝑉'), где 𝑉' - количество узлы в связном компоненте, где вы начинаете поиск. Это O(𝑉), когда граф связен.

Что касается приоритетной очереди: это не гарантируется. Поскольку вы помечаете узлы как посещенные только тогда, когда извлекаете их из очереди, вы потенциально можете иметь несколько вхождений одного и того же узла в очереди в определенный момент. Ограничение на количество вызовов heappush определяется количеством ребер. Таким образом, мы имеем наихудшую космическую сложность O(𝐸) для приоритетной очереди.

И если бы мне пришлось создать список смежности в Python с помощью dict, имела бы пространственная сложность O(E), где E — количество ребер?

Это зависит от того, создаете ли вы dict-keys для узлов, у которых нет исходящих ребер (с пустыми списками в качестве значений). Если да, то это Θ(𝑉+𝐸). Если вы опустите ключи, которые представляли бы такие узлы (без исходящих ребер), то это действительно Θ(𝐸), но тогда ваша программа должна иметь проверку, существует adj_list[cur] или нет.

Другие замечания

• Вам не нужно вызывать heapify, если в вашем списке всего один элемент. Список с одним элементом уже является допустимой кучей.

• Когда вы извлекаете узел из очереди, вам следует проверить, был ли он уже посещен. Это могло произойти, когда узел был помещен в очередь несколько раз (поскольку он встречался по разным путям), прежде чем из него было извлечено первое вхождение. В этом случае вы пометите его как посещенный, поскольку первое вхождение будет извлечено из очереди, но затем оно может в конечном итоге быть извлечено во второй раз: и тогда вам не следует его обрабатывать.

• Когда вы найдете целевой узел и у вас есть res, вам следует выйти из цикла.

• Вместо присвоения res было бы неплохо обернуть этот код в функцию и вернуть это значение.

Так:

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