有一些随机分布的据点,两点之间距离至少为10,则4个据点两两连线距离之和最小为?
时间: 2023-05-27 07:05:37 浏览: 178
求三角形内一点到三个顶点距离之和的最小值.doc
这是一个经典的最小生成树问题。最小生成树是连接一个无向连通图所有结点的一棵生成树,所选边的权值之和最小。
解法:
1.将所有据点之间的距离计算出来,如果距离小于10则将其权值设为正无穷,否则设为实际距离。
2.使用Prim或Kruskal算法求出最小生成树,并将所选边的权值之和返回。
注意:如果有多个联通分量,则需要对每个联通分量分别求最小生成树,然后将所选边的权值之和相加。
阅读全文