我正在尝试解决以下图形练习：
在无向加权图中，有 V 个顶点和 E 条边。找到访问 T(T<=V) 个顶点所需的最小权重，从标记为 0 的顶点开始。此外，如果两个访问过的顶点之间存在边，则其权重设置为 0。
这不是一个经典的旅行商问题，因为添加了一个条件，即如果您访问两个顶点，它们之间的边的权重会减小到 0。
如果 T == V，则使用 Prim 的最小生成树算法解决该问题，但由于您不必访问所有顶点，因此这并不总是返回最小权重。
我考虑过找到最小生成树，然后切割不会妨碍我到达所有“目标”顶点的能力的每条边，但这似乎过度并且可能不正确。
有什么想法吗？
编辑：我会给你一个例子。假设我们有一个带有 4 个顶点标记为 0,1,2 和 3 的图。我们有以下边（从，到，权重）： (0,1,1) (0,2,2) (1,3,4 ) (2,3,1) 最小生成树将包含边：(0,1,1)、(0,2,2) 和 (2,3,1)。有了它，每个顶点都可以从 0 开始到达。但是，练习的目标是达到 T 个顶点。话虽如此，例如，我们可能只需要到达顶点 2 和 3，从而不需要边 (0,1,1)，因此到达目标顶点所需的总权重是 2+1，而不是 1 +2+1。