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被实现为堆数据结构：

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

因此空间复杂度为 O( n )，其中n是优先级队列中的元素数量。您的实现可能会在优先级队列中多次存储一个顶点，但每个顶点只能添加与它的边数相同的次数，因此空间复杂度为 O(E)，其中 E 是优先级队列中的边数。图形。

原则上可以将空间复杂度提高到 O(V)，其中 V 是顶点数；为此，您可以实现一个增强优先级队列，它使用字典来维护堆中每个顶点的当前索引，允许按值删除（而不是仅轮询最小元素）。

顺便说一句，queue.PriorityQueue这是一个用于并发访问的同步实现。Dijkstra算法不需要并发优先级队列，因此你的算法将更加高效（在运行时间上），而无需同步开销；您可以heapq直接使用该模块在列表中实现优先级队列，分别使用heappush和heappop函数进行入队和 poll-min。