Dijkstra算法中优先级队列的空间复杂度

Question

谁能告诉我这个Dijkstra算法中优先级队列的空间复杂度。请注意，此处可以将一个顶点添加到队列中超过一次。但是，由于访问集，它的处理时间不超过一次。这就是为什么我想知道队列的最大大小可以得到的原因。

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 not in visited:
            for adj in adjList[parent]:
                child, cost = adj
                priorityQueue.put((cost + costPar, child))

        visited.add(parent)

Answer 1

queue.PriorityQueue类被实现为queue.PriorityQueue：

使用优先级队列，条目将保持排序（使用heapq模块），并且首先检索值最低的条目。

因此空间复杂度为O（n），其中n是优先级队列中的元素数。 Dijkstra的算法可以潜在地一次将所有图的顶点存储在优先级队列中，因此空间复杂度为O（V），其中V是图中的顶点数量。