最小权重连通子集 T 的边算法

Question

3

考虑在加权连通图G中找到一个最小权重的连接子集T的问题。T的权重是T中所有边的权重之和。 (a) 为什么这个问题不仅仅是最小生成树问题？提示：考虑负权重边。 (b) 给出一种有效的算法来计算最小权重连接子集T。

(c) 来自Sciena手册

(a) 最小生成树问题只能使树的总权重最小化，但是“最小权重连接子集”需要考虑每对路径的权重，因此我们可以重复使用同样的负边来减少每对路径的权重吗？

(b) 决策很明显：运行Dijkstra算法n次，跟踪以前的每对最短路径。似乎不是最好的方法，另一个想法是将所有边排序，从最大的开始 - 尝试删除每个并检查连通性...

- yetanothercoder

4

您有什么问题？我们不会为您完成家庭作业！ - templatetypedef

我认为寻找最短路径不太可行。所选边不一定要形成两个节点之间的简单路径。例如：1 - 2 (-1); 2 - 3 (-2); 2 - 4 (-4)，你需要选择所有的边，但它们并不构成一条路径。因此，我认为这不涉及路径，至少不是一种非常明显的方式。 - IVlad

1

我无法解析你对(a)的回答。你能否澄清一下？ - Ishtar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Foo Bah · Answer 1

针对部分A：

考虑每条边权重为-1的K3（三角形）。

最小生成树是什么，最小权重连接子集是什么？