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

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 increasinglyfor 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。