使用数组的Dijkstra算法的时间复杂度为O(V^2),如果实现了优先队列,我们可以进一步将复杂度提高到O(E log V)。但它的空间复杂度如何呢?在两种情况下都是O(V)吗?
使用数组的Dijkstra算法的时间复杂度为O(V^2),如果实现了优先队列,我们可以进一步将复杂度提高到O(E log V)。但它的空间复杂度如何呢?在两种情况下都是O(V)吗?
然而,(E >= V - 1),所以|V| + |E|等同于|E|。但通常我们会同时使用V和E。
O(V) + O(V) = O(2V) =~ O(V)
。更新:
它应该是o(V)。
见https://cs.au.dk/~gerth/papers/fun22.pdf
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