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

Question

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

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 class is implemented as a heap data structure:

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

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

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

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

Answer 2

你是出于好奇才问的吗？或者只是有性能问题？我是一名硬件加速专家，我在 HW 中实现了 Dijkstra 引擎，它可以在 AWS 中运行。请看GraphSim。它比领先图形数据库的软件实现快 100 倍。

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

Space Complexity of the Priority Queue in this Dijkstra Algorithm

dijkstra

space-complexity