使用数组的Dijkstra算法的时间复杂度为O(V^2)，如果实现了优先队列，我们可以进一步将复杂度提高到O(E log V)。但它的空间复杂度如何呢？在两种情况下都是O(V)吗？
Dijkstra算法的空间复杂度是多少？
6
- troopers97
1
2你自己分析了吗？试着计算一下算法应该存储哪些值，展示给我们你的方法。 - Ivan Smirnov
3个回答
4
Dijkstra算法的时间和空间复杂度：
- 时间：O((|V| + |E|) log V)
- 空间：O(|V| + |E|)
然而，(E >= V - 1)，所以|V| + |E|等同于|E|。但通常我们会同时使用V和E。
- Manmay Barot
2
如果您使用MinHeap（也称为优先队列）来实现Disjkstra的最短路径算法，该算法又使用数组来存储堆，并且如果您使用数组来存储图中每个节点的最短距离值，则空间复杂度将为
O(V) + O(V) = O(2V) =~ O(V)。- PiJei
1
更新：
它应该是o(V)。
见https://cs.au.dk/~gerth/papers/fun22.pdf
在改进版本中，我认为空间复杂度应该是O（V ^ 2），在最坏情况下，假设每个节点都与其它节点相连，因为我们可以设计一个图，使得每个节点未被放松到最小值时成为当前节点的邻居，并且这个操作可以重复进行V次循环。也就是(V-2) + (V-3) + ... + 2 + 1，即O（V ^ 2）。但我不确定。
EXAMPLE (undirected, directed is also good):
adjacency list:
0: {0, 0}, {1, 64}, {2, 128}, {3, 256}
1: {0, 64}, {1, 0}, {2, 32}, {3, 16}
2: {0, 128}, {1, 32}, {2, 0}, {3, 8}
3: {0, 256}, {1, 16}, {2, 8}, {3, 0}
0 is the source
Init:
dis: 0 -1 -1 -1
heap: {0, 0}
EXECUTION:
dis: [0] 64 128 256
heap: {64, 1}, {128, 2}, {256, 3} size: +3 -1
dis: [0] [64] 96 80
heap: {80, 3}, {96, 2}, {128, 2}, {256, 3} size: +2 -1
dis: [0] [64] 88 [80]
heap: {88, 2}, {96, 2}, {128, 2}, {256, 3} size: +1 -1
dis: [0] [64] [88] [80]
heap: {96, 2}, {128, 2}, {256, 3} size: +0 -1
- Yude Wei
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接