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

Question

有人能告诉我这个Dijkstra算法中优先队列的空间复杂度吗？请注意，一个顶点可能会被添加到队列多次。但由于visited集合的存在，它不会被处理多次。这就是为什么我想知道队列的最大大小。

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)

- cs guy

Answer 1

queue.PriorityQueue类是使用堆数据结构实现的：

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

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

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

---

作为附注，queue.PriorityQueue 是一个用于并发访问的同步实现。Dijkstra算法不需要并发优先队列，因此在没有同步开销的情况下，您可以直接使用heapq模块在列表中实现优先队列，使用heappush和heappop函数分别进行入队和出队操作，这样您的算法将更加高效（运行时间）。

- kaya3

Answer 2

你是出于好奇还是存在性能问题而在询问吗？ 我是一个硬件加速的人，我在硬件上实现了Dijkstra引擎，在AWS上可以运行。请看 GraphSim。它比主流图形数据库的软件实现快100倍。

- max nigri