给定无向图与可选边集，如何选择最优边添加最小化最短路径

逐边插入原图副本、对每条候选边单独跑一次Dijkstra求最短路的方法，核心问题是重复做了大量无意义的全图计算——毕竟插入一条边带来的路径变化，本质只会影响所有经过这条新边的路径，完全没必要每次都把整张图的最短路重算一遍。

整个优化流程只需要两次全图最短路计算，后续所有候选边的评估全部基于预存的距离值快速推导：

• 从固定起点s出发，在原图上跑一次Dijkstra，记录所有节点到s的最短距离，存入数组dist_s
• 构建原图的反向边集合，从固定目标点t出发跑一次Dijkstra，记录所有节点到t的最短距离，存入数组dist_t
• 先把原图本身的s-t最短路径长度original_dist = dist_s[t]记下来作为基准值

对候选边集合里的每一条边(a, b, w)（a、b为边端点，w为边权重），不用插边跑算法，直接算插入这条边后能拿到的最优s-t路径长度：

该候选边对应的最优路径值 = min(original_dist, dist_s[a] + w + dist_t[b], dist_s[b] + w + dist_t[a])
（如果是有向边，只需要保留对应方向的计算项，反向的项直接忽略）

计算过程中如果任意一段的距离是无穷大（代表该段在原图中不可达），直接跳过对应的计算项就行。

两种方案的开销差异非常明显：

• 原方案的总复杂度为O(m*(M + N log N))，m是候选边总数，N是图节点数，M是图原有边数，开销会随着候选边数量增加线性放大
• 优化后方案的总复杂度为O(M + N log N + m)，仅需两次Dijkstra的固定开销，后续遍历候选边的计算量都是常数级，哪怕候选边规模很大，总开销也几乎不会上涨

等所有候选边都算完，直接取算出的最优路径值最小的那条边，就是能让总权重表现最好的待加边，全程不需要构建图副本，也不需要重复运行Dijkstra。

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