dijkstra算法的时间复杂度？

Question

考虑到优先级队列可以达到| E |，这个Dijkstra代码的时间复杂度是多少？（节点可能多次添加到优先级队列）我想解释一下while循环中的时间复杂性

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

下面的for循环最多可以运行| 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 |）

Answer 1

每个顶点最多执行一次内部循环。其迭代总数是每个顶点的度数之和，等于边数的两倍。因此，它最多执行2*E次

行priorityQueue.put((cost + costPar, child))在堆中插入一个节点，这是一个O(log(size_of_heap))操作。注意size_of_heap<=E

结合以上内容，我们得到O(|E| * log |E|)