算法:将州内所有城市连接到该州两个机场之一的最小道路长度

Question

假设一个州有10个城市A,B,C,D,E,F,G,H,I,J.现在让我们说D和G都有一个机场.考虑到每个城市之间的距离,应该建造的最小道路长度是多少,以便所有城市都连接到机场？从每个城市到机场可以有直接路线或间接路线(即通过其他城市); 我们的目标是建造最小的道路长度.

Answer 1

通过简单地将与机场边缘重量相关的顶点链接在一起,可以将问题简化为最小生成树问题.因此,您可以使用例如经典的Prim算法来解决它:

1. 使用包含机场的所有顶点初始化解决方案
2. 在所有剩余边缘中,选择增加生成树的最便宜的边缘
3. 迭代直到覆盖每个顶点.