我正在学习最小生成树。我通过 Prim 的加权有向图算法。
算法很简单
- 您有两组顶点，已访问和未访问
- 将所有边的距离设置为无穷大
- 从未访问集中的任何顶点开始并探索其边缘
- 在所有边中，如果目标顶点未被访问并且边的权重小于目标顶点的距离，则使用边的权重更新目标顶点的距离
- 选择距离最小的未访问顶点，然后再做一次，直到所有顶点都被访问
相信通过上述算法，我将能够在所有生成树中找到成本最小的生成树，即最小生成树。
但是我将它应用于以下示例，我认为它失败了。
考虑以下示例
顶点是 {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被访问并且（顶点，距离）=>
（v2，8）
（v3，15）
（v4，7）
现在v4的距离最小即7，所以我探索v4，它对v5有优势，所以会发生以下修改
访问顶点v4并且（顶点，距离）=>（v5,7）
现在在所有 v5 中距离最短，即 7 ，所以我探索 v5 并且它没有任何边缘，所以我只是将它标记为已访问
访问顶点 v5
现在，混乱从这里开始
距离最小的顶点现在是 v2，它的边到 v5，权重为 4，当前 v5 的距离为 7，之前由边 (v4,v5) : 7 分配，所以，我相信要制作最小生成树, v5 的距离应该从 7 更新到 4 为 4 < 7 但它不会因为 v5 已经被访问过并且 Prim 算法不更新已经访问过的顶点的距离并且 v5 的距离将保持 7 而不是 4而且这棵树不会有最低成本
我做对了吗？还是我做错了什么？
谢谢
