Prim和Dijkstra图算法的区别

Question

我正在阅读Cormen的图算法书。下面是该书中的伪代码。

Prim算法用于最小生成树

MST-PRIM (G, w, r)

for each u in G.V
  u.key = infinity
  u.p = NIL

r.key = 0
Q = G.V
while Q neq null
  u = EXTRACT-MIN(Q)
  for each v in G.Adj[u]
    if (v in Q) and (w(u,v) < v.key)
      v.p = u
      v.key = w(u,v)

迪杰斯特拉算法用于查找单源最短路径。

INITIALIZE-SINGLE-SOURCE (G,s)
  for each vertex v in G.V
    v.d = infinity
    v.par = NIL
  s.d = 0

DIJKSTRA (G, w, s)
  INITIALIZE-SINGLE-SOURCE(G,s)
  S = NULL
  Q = G.V
  while Q neq null
    u = EXTRACT-MIN(Q)
    S = S U {u}
    for each vertex v in G.Adj[u]
      RELAX(u,v,w)

我的问题是，为什么我们要检查顶点是否属于Q (v in Q)，也就是说该顶点不属于树，而在Dijkstra算法中我们没有检查这个条件。

有任何原因吗？

- venkysmarty

---

你是不是想说 'Prim' 而不是 'Prism'？ - Codor

Answer 1

所谓的Prim算法和Dijkstra算法首先解决不同的问题。'Prim'算法用于寻找无向图的最小生成树，而'Disjkstra'算法则解决有向图中非负边权的单源最短路径问题。

- Codor

Answer 2

在这两个算法中，队列Q包含所有尚未“完成”的顶点，即根据常用术语（参见此处），白色和灰色。

在Dijkstra算法中，黑色顶点不能被放松，因为如果可以的话，这意味着其距离事先不正确（与黑色节点属性矛盾）。因此，您检查v in Q与否没有区别。

在Prim算法中，有可能找到一条小权重的边，导致已经是黑色顶点。这就是为什么如果我们不检查v in Q，那么顶点v中的值确实会改变。通常，这并不重要，因为我们从不为黑色顶点读取最小权重值。然而，您的伪代码正在使用MinHeap数据结构。在这种情况下，每个顶点值的修改都必须伴随着DecreaseKey。很明显，无法为黑色顶点调用DecreaseKey，因为它们不在堆中。这就是为什么我认为作者决定明确检查v in Q的原因。

总的来说，Dijkstra算法和Prim算法的代码通常是完全相同的，除了细微的差异：

• Prim算法在RELAX中检查w（u，v）是否小于D（v）。
• Dijkstra算法在RELAX中检查D（u）+ w（u，v）是否小于D（v）。

- stgatilov

---

感谢您的解释。为什么在Prim算法的for循环中要检查v是否属于Q？ - venkysmarty

@venkysmarty：如果 v 不属于 Q，那么它是一个新的顶点（之前没有见过）。在这种情况下，我们必须在 if 语句内执行所有操作，并将其放入 Q 中。奇怪的是，这在您发布的伪代码中缺失了。 - stgatilov

@stgatilov 对不起，我还是没明白。伪代码中缺少什么，请您纠正一下。我认为如果顶点属于要添加到树中的Q集合，那么... - venkysmarty

@venkysmarty，我已经添加了你特定问题的解释。 - stgatilov

Answer 3

请看我用C++编写的Dijkstra和Prim算法的个人实现。

它们非常相似，我将Dijkstra修改为Prim。

Dijkstra：

const int INF = INT_MAX / 4;
struct node { int v, w; };
bool operator<(node l, node r){if(l.w==r.w)return l.v>r.v; return l.w> r.w;}

vector<int> Dijkstra(int max_v, int start_v, vector<vector<node>>& adj_list) {
    vector<int> min_dist(max_v + 1, INF);  
    priority_queue<node> q;
    q.push({ start_v, 0 });  
    min_dist[start_v] = 0;   
    while (q.size()) {
        node n = q.top(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (min_dist[adj.v] > n.w + adj.w) {
                min_dist[adj.v] = n.w + adj.w;
                q.push({ adj.v, adj.w + n.w });
            }
        }
    }
    return min_dist;
}

Prim：

struct node { int v, w; };
bool operator<(node l, node r) { return l.w > r.w; }
int MST_Prim(int max_v, int start_v, vector<vector<node>>& adj_list) {
    vector<int> visit(max_v + 1, 0);
    priority_queue<node> q; q.push({ start_v, 0 });
    int sum = 0;  
    while (q.size()) {
        node n = q.top(); q.pop();
        if (visit[n.v]) continue;  
        visit[n.v] = 1;
        sum += n.w;
        for (auto adj : adj_list[n.v]) {
            q.push({ adj.v, adj.w });  
        }
    }
    return sum;
}

- CodingLab