满足通行距离约束的道路建设成本最小化图算法咨询

你的问题属于带直径约束的最小成本网络增广问题，核心约束是最终路网的直径（任意两点间最短通行距离的最大值）严格小于N，只能从给定候选道路集合里选边修建，目标是总建设成本最低，可按数据规模选对应方案：

前置预处理步骤 #

不管用什么算法，先做两步预处理减少冗余计算：

• 先基于现有双向道路计算全源最短路径：节点数少就用Floyd-Warshall算法，节点多就对每个节点跑一次Dijkstra，把初始点对最短距离存在initDist[i][j]数组里
• 筛除无效候选道路：如果某条候选道路连接u、v，自身通行距离为w，且初始状态下u到v的最短路径已经小于等于w，这条道路修完不会缩短任何两点的通行距离，直接移出候选池即可。

小规模场景（城市数≤30，候选道路数≤200） #

用精确算法求全局最优解即可：

• 最容易实现的是分支定界法：先把所有候选道路按建设成本从低到高排序，递归遍历每条路选/不选的分支，每次选完一条路就更新当前的全源最短路径，一旦当前路网已经满足所有点对通行距离<N，就记录当前总成本作为可行解上界，后续递归分支如果累计成本已经超过当前上界直接剪枝终止，效率足够应付小规模数据。
• 如果熟悉整数规划建模，也可以直接给每条候选路设0-1决策变量，把「任意点对最短路径<N」作为约束，调用求解器直接算最优解。

中大规模场景（城市数≤200，候选道路数≤2000） #

精确算法时间复杂度太高，用启发式算法求可用的近优解即可：

1. 先构造初始可行解：从初始路网出发，每次迭代计算所有未选候选路的「性价比」——即修完这条路之后，全局路网直径下降的数值除以这条路的建设成本，选性价比最高的路修建，更新全源最短路径，直到路网直径满足<N的要求，得到初始可行解。
2. 做局部优化降本：遍历当前已选的所有候选路，依次尝试临时删除这条路，若删除后路网直径仍满足约束，就永久删除这条路降低成本；如果删除后不满足约束，就尝试把这条路替换成其他未选的候选路，只要替换后仍满足直径约束且总成本更低就执行替换，反复迭代直到没有可优化的空间。
3. 若对解的质量要求更高，可以加简单的模拟退火逻辑：迭代过程中以一定概率接受暂时让成本小幅上升的替换，避免陷入局部最优，通常能得到成本更低的解。

注意不要误用普通最小生成树（MST）类算法：普通MST仅保证全连通且总边权最小，既不支持路网直径的硬约束，也无法适配「已有固定道路+候选边选子集」的增广场景，完全不匹配该问题的需求。

内容的提问来源于stack exchange，提问作者Vasiliy Platon