在无向图中有负边的地方求一棵最小权生成树

Question

所以我需要解决这个问题，我对如何解决它有一个大概的想法，但如果我做错了，请纠正我。

所以要找到 MST，我需要在图上执行 Kruskals 算法

这是我对这个 Kruskals 算法的伪代码

克鲁斯卡尔(V,E) A = 空；对于每个 v 包含在 V 制作不相交的集合（v）按权重递增排序E 对于每个（v1，v2）包含在 E 如果

  Kruskal(V,E)

A = null;
for each v contains in V
     make disjoint set(v)
Sort E by weight increasingly
for each(v1, v2) contains in E 
     if Find(v1) is not equal to Find(v2)
          A = A Union {(v1,v2)}
          Union(v1,v2)
Return A

所以我做的第一件事就是找到距离最短的节点，对吗？

1)

我假设 S 到 H 的距离最短，因为 d(h,s) = -3

所以 A = {(h,s)}

所以现在我们遵循这个模式

2) A = {(h,s),(s,f)}

3) A = {(h,s),(s,f)(s,n)}

4) A = {(h,s)(s,f)(s,n)(f,k)}

5) A = {(h,s)(s,f)(s,n)(f,k)(s,m)}（我们跳过 H 到 N，因为路径已经从 h到 n 是通过 s )

6) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)}

7) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)(b,m)}

所以现在既然有一条连接所有边的路径，我们就可以了吗？

但我不明白的是有距离[u,v]比通过多个顶点的路径[u,v]更短。例如 d[d,m] 比先经过 B 的 p[d,m] 短。我做错了什么吗？

Answer 1

你没有做错任何事。无法保证 MST 保留节点之间的最短距离。例如：边权重为 3、2、2 的三节点完整图 ABC（为我的 ascii 艺术道歉）：

A --- 2 --- B
|           |
2          /
|         /
C----3---/

最小生成树是C-A-B，但是原图B和C的距离是3，MST是4。

在无向图中有负边的地方求一棵最小权生成树

Find a minimum weight spanning tree in the undirected graph where there are negative edges

algorithm

graph

kruskals-algorithm