这个 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|)

这个 dijkstra 算法的时间复杂度？

Time Complexity of this dijkstra algorithm?

python

dijkstra

time-complexity