Dijkstra 的空间复杂度

Question

我正在做 Dijkstra 算法的一些 Leetcode 问题，我不太明白它的空间复杂度。我上网查了一下，但找到了各种各样的答案，有些答案相当复杂，所以我想知道我是否理解正确。

# initialize maxheap
maxHeap = [(-1, start_node)]
heapq.heapify(maxHeap)

# dijkstras algorithm
visit = set()
res = 0
while maxHeap:
    prob1,cur = heapq.heappop(maxHeap)
    visit.add(cur)

    # update result
    if cur == end_node: 
        res = max(res, -1 * prob1)

    # add the neighbors to the priority queue
    for nei,prob2 in adj_list[cur]:
        if nei not in visit: heapq.heappush(maxHeap, (prob1 * prob2, nei))

由于我使用

visit

集和

priority queue

来跟踪节点，空间复杂度是否只是 O(V)，其中 V 是图中的顶点数？如果我必须使用

dict

在 Python 中生成邻接表，其空间复杂度是否为 O(E)，其中 E 是边数？

Answer 1

是的，Dijkstra 算法的一个（有时相关的）缺点是它可能占用与搜索空间大小成比例的空间量。这是（有时）选择迭代加深深度优先搜索的原因之一 - 还有其他原因，但最坏情况的空间使用就是其中之一。

如果你有一个显式图，那么 Dijkstra 算法的空间使用并不是什么大问题，因为如果你有一个显式图，那么显然该图没有那么大，所以 Dijkstra 所使用的空间也不可能那么大。

如果我必须使用字典在 Python 中生成邻接列表，其空间复杂度是否为 O(E)，其中 E 是边数？

是的，但是你呢？没有规则规定在运行 Dijkstra 之前必须提前准备好邻居列表，您（通常）可以在 Dijkstra 请求时按需生成邻居，然后空间使用就不再是问题了。基本上，您可以（通常）用函数调用

adj_list[cur]

替换

generateNeighbours(cur)

，而无需更改算法的任何内容，只要您可以按需生成节点的邻居即可。对于任意预先存在的图，情况并非如此，但通常（当然，并非总是，只是经常）在隐式图上使用最短路径算法，例如状态空间图或对应于连接相邻单元的规则网格。也许这没有多大意义，但就我个人而言，我只在隐式图上使用过最短路径算法。