dijkstra 算法 运行 数组和优先级队列的时间
dijkstra's algorithm running time with array and priority queue
我很难理解 dijkstra 算法的时间。下面我放了我正在分析数组的伪代码。考虑到 V 是顶点，E 是边。作为数组的 Q 的初始化时间为 O(V)，最小值和 while 内部的 for 将具有 O(V) of while 时间 O(V + E)，则结果将为 O(V²)，am我说对了吗？
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // Initialization
3
4 create vertex set Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // Unknown distance from source to v
9 prev[v] ← UNDEFINED // Predecessor of v
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // The main loop
15 u ← Q.extract_min() // Remove and return best vertex
16 for each neighbor v of u: // only v that is still in Q
17 alt ← dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist[], prev[]
下面是我分析优先级队列的伪代码。现在，作为优先级队列的 Q 的初始化时间为 O(V)，最小值和 while 内部的 for 将具有 O(V) 的 while 时间 O(1 + ElogV)，那么结果将是 O(VElogV ）， 我对么？考虑到最坏情况是E = (V - 1)，那么结果不可能是O(V²logV)，为什么我在网上查到的值是O(ElogV)？为什么优先队列比数组快？
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph: // Initialization
6 dist[v] ← INFINITY // Unknown distance from source to v
7 prev[v] ← UNDEFINED // Previous node in optimal path from source
8 add v to Q // All nodes initially in Q (unvisited nodes)
9
10 dist[source] ← 0 // Distance from source to source
11
12 while Q is not empty:
13 u ← vertex in Q with min dist[u] // Node with the least distance
14 // will be selected first
15 remove u from Q
16
17 for each neighbor v of u: // where v is still in Q.
18 alt ← dist[u] + length(u, v)
19 if alt < dist[v]: // A shorter path to v has been found
20 dist[v] ← alt
21 prev[v] ← u
22
23 return dist[], prev[]
The Q as an array has its initialization with time O(V), the minimum and the for inside the while would have O(V) of while times O(V + E), then the result would be O(V²), am I correct?
如果那是正确的，时间复杂度将是 O(V² + VE)，并且 O(VE) 将占主导地位（因为 'useful' 图上的 V <= E），给你 O(VE) 用于整个算法。但是你的分析不正确，这就是为什么最终的时间复杂度是 O(V²).
你是正确的，WHILE 循环内的 min() 操作有 O(V)，因此整个算法 O(V²)，但 FOR循环，它是 O(E) 算法的整个持续时间，而不是单独的迭代。这是因为您恰好从 Q 中删除了每个顶点一次，并且您检查了每个删除的顶点的所有出边。换句话说，您检查所有边，因此 O(E).
Now, the Q as an priority queue has its initialization with time O(V), the minimum and the for inside the while would have O(V) of while times O(1 + ElogV), then the result would be O(VElogV), am I correct?
没有。 min() 操作和 FOR 循环的时间复杂度取决于使用什么数据结构作为优先级队列。假设你使用一个最小堆作为优先级队列，min() 将占用 O(logV)，而 FOR 循环将占用总计 O(ElogV)，这占主导地位，并且成为算法的总时间复杂度。
这是另一个答案的 link，它解释了如何根据您用于实现优先级队列的数据结构来分析 Dijkstra 算法的时间复杂度：
我很难理解 dijkstra 算法的时间。下面我放了我正在分析数组的伪代码。考虑到 V 是顶点，E 是边。作为数组的 Q 的初始化时间为 O(V)，最小值和 while 内部的 for 将具有 O(V) of while 时间 O(V + E)，则结果将为 O(V²)，am我说对了吗？
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // Initialization
3
4 create vertex set Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // Unknown distance from source to v
9 prev[v] ← UNDEFINED // Predecessor of v
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // The main loop
15 u ← Q.extract_min() // Remove and return best vertex
16 for each neighbor v of u: // only v that is still in Q
17 alt ← dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist[], prev[]
下面是我分析优先级队列的伪代码。现在，作为优先级队列的 Q 的初始化时间为 O(V)，最小值和 while 内部的 for 将具有 O(V) 的 while 时间 O(1 + ElogV)，那么结果将是 O(VElogV ）， 我对么？考虑到最坏情况是E = (V - 1)，那么结果不可能是O(V²logV)，为什么我在网上查到的值是O(ElogV)？为什么优先队列比数组快？
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph: // Initialization
6 dist[v] ← INFINITY // Unknown distance from source to v
7 prev[v] ← UNDEFINED // Previous node in optimal path from source
8 add v to Q // All nodes initially in Q (unvisited nodes)
9
10 dist[source] ← 0 // Distance from source to source
11
12 while Q is not empty:
13 u ← vertex in Q with min dist[u] // Node with the least distance
14 // will be selected first
15 remove u from Q
16
17 for each neighbor v of u: // where v is still in Q.
18 alt ← dist[u] + length(u, v)
19 if alt < dist[v]: // A shorter path to v has been found
20 dist[v] ← alt
21 prev[v] ← u
22
23 return dist[], prev[]
The Q as an array has its initialization with time O(V), the minimum and the for inside the while would have O(V) of while times O(V + E), then the result would be O(V²), am I correct?
如果那是正确的，时间复杂度将是 O(V² + VE)，并且 O(VE) 将占主导地位（因为 'useful' 图上的 V <= E），给你 O(VE) 用于整个算法。但是你的分析不正确，这就是为什么最终的时间复杂度是 O(V²).
你是正确的，WHILE 循环内的 min() 操作有 O(V)，因此整个算法 O(V²)，但 FOR循环，它是 O(E) 算法的整个持续时间，而不是单独的迭代。这是因为您恰好从 Q 中删除了每个顶点一次，并且您检查了每个删除的顶点的所有出边。换句话说，您检查所有边，因此 O(E).
Now, the Q as an priority queue has its initialization with time O(V), the minimum and the for inside the while would have O(V) of while times O(1 + ElogV), then the result would be O(VElogV), am I correct?
没有。 min() 操作和 FOR 循环的时间复杂度取决于使用什么数据结构作为优先级队列。假设你使用一个最小堆作为优先级队列，min() 将占用 O(logV)，而 FOR 循环将占用总计 O(ElogV)，这占主导地位，并且成为算法的总时间复杂度。
这是另一个答案的 link，它解释了如何根据您用于实现优先级队列的数据结构来分析 Dijkstra 算法的时间复杂度：