Сложность времени этого алгоритма dijkstra? - PullRequest
Новая
       12

Сложность времени этого алгоритма dijkstra?

0 голосов
/ 31 марта 2020

Какова временная сложность этого кода Дейкстры, учитывая, что очередь с приоритетами может достигать размера | E |? (Узлы, вероятно, будут добавлены более одного раза в очередь с приоритетами) Я хочу обосновать временную сложность внутри while l oop. 

def shortestReach(n, edges, start,target):

    adjList = collections.defaultdict(list)

    for parent, child, cost in edges:
        parent -= 1
        child -= 1
        adjList[parent].append((child, cost))
        adjList[child].append((parent, cost))

    priorityQueue = queue.PriorityQueue()
    priorityQueue.put((0, start))
    visited = set()
    while priorityQueue.qsize() > 0:
        costPar, parent = priorityQueue.get()

        if parent == target:
            return costPar

        if parent in visited:
            continue

        for adj in adjList[parent]:
            child, cost = adj
            if child not in visited:
                priorityQueue.put((cost + costPar, child))

        visited.add(parent)

Моя идея: поскольку priorityQueue может быть настолько большим, насколько | E |, то строка ниже может произойти не более | E | время, но узлы, взятые из очереди, не будут обрабатываться, так как у нас есть проверка посещенных множеств. так что | E | log | E | 

costPar, parent = priorityQueue.get()

для l oop ниже, самое большее, может работать при | E | время, так как каждый узел обрабатывается только один раз из-за посещенного набора, поэтому причина в том, что он может занять до | E | log | E | не более 

for adj in adjList[parent]:
            child, cost = adj
            if child not in visited:
                priorityQueue.put((cost + costPar, child))

общая сложность времени составляет 2 * | E | log | E | -> O (| E | log | E |)?

1 Ответ

1 голос
/ 31 марта 2020

Внутренний l oop выполняется не более одного раза для каждой вершины. Общее количество его итераций представляет собой сумму степеней каждой вершины, которая равна удвоенному числу ребер. В результате он выполняется не более 2*E раз.

Строка priorityQueue.put((cost + costPar, child)) вставляет узел в кучу, что является операцией O(log(size_of_heap)). Обратите внимание, что size_of_heap<=E

Комбинируя вышесказанное, получаем O(|E| * log |E|)

...