使用数组的Dijkstra算法的时间复杂度为O(V^2(，如果实现了优先级队列，我们可以进一步将复杂度提高到O(E log V(。但是它的空间复杂性呢？在这两种情况下都是O(V(吗？
Dijkstra 算法的时间和空间：
- 时间：O((|V|+ |E|(日志 V(
- 空格：O(|V|+ |E|(
但是，(E>= V - 1( 所以 |V|+ |E|==> |E|.但通常我们同时使用 V 和 E
如果您使用MinHeap(又名优先级队列(实现 Disjkstra 的最短路径算法，该算法又使用数组来存储堆，并且如果您使用数组来存储图形中每个节点的最短距离值，则空间复杂度将O(V) + O(V) = O(2V) =~ O(V)
更新：
它应该是 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