algorithm - Dijkstra 和 Prim 算法

Question

据我所知，Dijkstra 和 Prim 的算法几乎相同。这是来自维基百科的伪代码，我将解释我的困惑。

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[]

Prim的算法几乎是一样的，为了方便，我就把第14行开始的循环改一下

14     while Q is not empty:                              
15         u ← Q.extract_min()                            
16         for each neighbor v of u:                      
17             if v ∈ Q and length(u, v) < cost[v]
18                 cost[v] ← length(u, v)
19                 prev[v] ← u
20                 Q.decrease_priority(v, length(u, v))

有两个更改，第一个是将 dist[] 替换为 cost[]，据我了解，这与算法解决不同问题的事实有关。第二个对我来说是模糊的，即 Dijkstra 算法中没有 if v ∈ Q 这个条件。我真的不明白为什么我们可以返回到 Prim 算法中的已访问顶点集，而这不能在 Dijkstra 算法中发生。

Answer 1

在 Dijkstra 中，我们计算 alt ← dist[u] + length(u, v) 并将 dist[v] 设置为 alt如果 alt 小于 dist[v] 的当前值。 alt 代表从起始节点到 v 的距离，如果我们通过 u。然而，u 是刚刚从Q 中取出的节点，因此，它与起始节点的距离大于或等于之前所有其他节点的距离从 Q 中取出。因为 Dijkstra 要求所有边的权重都是非负的，所以 alt 保证大于或等于 dist[v] 如果 v 不在Q 因为它是 dist[u] 和 length(u, v) 的和，所以它不会传递条件如果。换句话说，如果 v 不在 Q 中，u 相对于我们已经拥有的路径 v.