dijkstra - 此 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类实现为 heap data structure :

With a priority queue, the entries are kept sorted (using the heapq module) and the lowest valued entry is retrieved first.

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

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

---

作为旁注，queue.PriorityQueue 是一个用于并发访问的同步实现。 Dijkstra 的算法不需要并发优先级队列，因此您的算法将更有效(在运行时)而无需同步开销；你可以使用heapq模块直接在列表中实现一个优先级队列，分别使用heappush和heappop函数来enqueue和poll-min。