一个无向图，从起点出发，要求经过的点数最多，前提是到这些点的距离，必须是起点到该点的最短距离。

Question

一个无向图，从起点出发，要求经过的点数最多，前提是到这些点的距离，必须是起点到该点的最短距离。即假设途中有经过A这个点，则此时从起点到A点所走的距离，必须是起点到A点的最短路径。该用干什么算法？求助？？？ 求能走到最多点数。

Answer 1

这是运筹学最小生成树的问题。

树：无圈的连接图。

解法：破圈法、避圈法、狄克拉斯法、逐次逼近法。

最常用的是破圈法：就是从小的环形开始，将环中最长边去掉，知道满足树的性质。