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))

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

Answer 1

不确定我的想法是否正确。对于 Dijkstra 和 prims 算法，我们应该只处理 Q 中的顶点。对于 Dijkstra 算法，伪代码可能没有明确检查当前顶点是否仍在 Q 中，但注释为 "only v that is still in Q"

 for each neighbor v of u:                      // only v that is still in Q

我假设它们与 x ∈ Q

的意思相同

17             if x ∈ Q and length(u, v) < cost[v]

如果这里的x代表第16行的"v"。

Answer 2

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

的路径来说就是绕了个弯。

Answer 3

Dijkstra 和 Prim 算法非常相似。

区别是：

Prim 算法： 通过无向边到最小生成树的最近顶点
Dijsktra 算法： 通过定向路径到源的最近顶点

资料来源：Sedgewick 和 Wayne 的算法

Dijkstra 和 Prim 算法

Dijkstra's and Prim's algorithm

algorithm

dijkstra

graph-algorithm