带有顶点权重和边权重的最小生成树

Question

带有顶点权重和边权重的最小生成树

4

我在解决最小生成树问题时遇到了一些困难。在一个图中，每个节点代表一个城市，可能会有带权重的边连接两个节点，这表示建造两个城市之间道路的成本。问题是要求建造道路的最小成本，并且使所有城市以某种方式相连。我可以使用Prim或kruskal算法轻松解决这个子问题。

现在出现了棘手的部分：每个城市（节点）都可以拥有一个机场，每个机场都有一次性成本（如果您决定建造它）。如果两个城市都有机场，则可以使用机场之间旅行。现在我必须计算建造道路和机场的最小成本，以便所有城市都能相互连接，但我很难将机场的连接与网络的其余部分表示出来。有人可以帮我吗？也许我在使用最小生成树方面完全错误？

我想到的唯一解决方案是：对于每个拥有机场的城市，我将该城市与其他拥有机场的城市相连。此外，如果建造两个机场的成本低于建造道路的成本，则我会考虑这种情况。我运行kruskal以获取最便宜的边缘，但如果kruskal选择了“机场”边缘，则我将其添加到生成树中，然后将两个机场的成本归零（如果它们以前没有被建造）。我相信，通过在运行kruskal时进行动态权重更改，我正在破坏获得最小成本的想法。

- joao deus

+1。顺便说一句，我可以确认你的算法在所有情况下都不会给出正确的结果：考虑三个城市，其中在任何一个城市建造机场的成本为3，而在任何两个城市之间建造道路的成本为5。最小成本是建造三个机场和没有道路（总成本=3 + 3 + 3 = 9），但由于在任何两个城市建造机场的成本比在它们之间建造道路更昂贵（成本=3 + 3 = 6 vs. 成本=5），因此你的算法将不会建造任何机场，而是建造两条道路（总成本=5 + 5 = 10），这是非最优的。 - ruakh

1个回答

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

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

- mcdowella · Accepted Answer

有两种可能性：

1）最优解不使用机场。在这种情况下，您可以忽略机场并像往常一样构建最小生成树。

2）最优解使用机场。在这种情况下，在图表中添加名为“sky”的虚拟节点。从任何城市到“sky”的道路建设成本就是建造机场的成本。使用机场的最优解的成本是在修改后的图表中最小生成树的成本。

因此，请尝试这两个选项并选择最小成本。