algorithm - 用于加权有向图的 Prim 算法

Question

我正在学习最小生成树。我通过 Prim 的加权有向图算法。

算法简单

• you have two set of vertices, visited and non-visited
• set distance for all edges to infinity
• start with any vertex in non-visited set and explore its edges
• In all edges, update distance of the destination vertex with the weight of the edge if destination vertex it is not visited and if weight of the edge is less than the distance of destination vertex
• pick the non-visited vertex with smallest distance and do it again until all vertex are visited

我相信通过上述算法，我将能够在所有生成树中找到具有最小成本的生成树，即最小生成树。

但是我把它应用到下面的例子中，我认为它失败了。

考虑下面的例子

顶点是{v1,v2,v3,v4,v5}，边的权重是
(x,y) : w =>
(v1,v2) : 8
(v1,v3) : 15
(v1,v4) : 7
(v2,v5) : 4
(v4,v5) : 7

首先我探索 v1，它有到 v2、v3、v4 的边，所以图变成了
顶点 v1 被访问并且 (vertex, distance) =>
(v2,8)
(v3,15)
(v4,7)

现在 v4 的距离最小，即 7，所以我探索 v4，它有 v5 的边，因此发生以下修改
访问顶点 v4 并且 (vertex, distance) => (v5,7)

现在在所有 v5 中距离最小，即 7，所以我探索 v5 并且它没有任何优势，所以我只是将其标记为已访问

顶点v5被访问

现在，困惑从这里开始

距离最小的顶点现在是 v2，它有到 v5 的边，权重为 4，目前 v5 的距离为 7，之前由边 (v4,v5) 分配:7，所以，我相信最小生成树，v5 的距离应该从 7 更新为 4，因为 4 < 7 但不会，因为 v5 已经被访问过，Prim 算法不会更新已经访问过的顶点的距离，v5 的距离将保持为 7而不是 4，这棵树将没有最低成本

我做对了吗？还是我做错了什么？

谢谢

Answer 1

首先我要提到的是 Prim 的算法只适用于无向图，所以如果我们认为该图是无向的，这是算法在您的案例中的逐步进展:

而且您应该考虑到，在有向图中多次找到最小生成树甚至是不可能的，但是对于有向图最接近 MST 的概念是最小成本树状结构。