当然有专门的算法能搞定这个问题！你描述的需求本质是最小化路径中的最大边权问题，这类问题有几种成熟的解法，我给你拆解一下：

解法一：二分查找 + 连通性验证 #

这是最直观易懂的思路，核心是通过二分枚举可能的最大步长，再验证该步长下能否从A走到B：

• 核心逻辑：我们要找最小的d，使得只保留所有长度≤d的边时，A和B是连通的。
• 具体步骤：
  1. 确定二分的上下界：下界设为0，上界设为A到B的直接距离（因为直接走AB的最大步长就是这个值，肯定是一个可行解）。
  2. 取区间中间值mid，构建一个子图：只保留所有长度≤mid的边。
  3. 用BFS或DFS遍历这个子图，检查A和B是否连通。
  4. 根据结果调整区间：如果连通，说明我们可以尝试更小的d，把上界设为mid；如果不连通，就需要增大d，把下界设为mid。重复这个过程直到区间收敛，最终得到的最小可行d就是答案。
• 适合场景：顶点数量不多的完全图，实现起来简单，不需要复杂的数据结构。

解法二：基于最小生成树（MST）的方法 #

这个方法利用了最小生成树的核心性质，效率更高，尤其适合多组点对查询的场景：

• 核心逻辑：在图的最小生成树中，任意两点之间的唯一路径，就是这两点间所有可能路径里最大边权最小的那条路径。
• 具体步骤：
  1. 对完全图构建最小生成树：可以用Prim算法（适合稠密图，完全图正好是稠密图，时间复杂度O(V²)）或者Kruskal算法（时间复杂度O(V² log V)）。
  2. 在生成好的MST中，找到A到B的路径，这条路径上的最大边权就是我们要找的答案。
• 原理补充：以Kruskal算法为例，它是按边权从小到大依次添加边的，当A和B第一次被连通时，最后添加的那条边就是路径中的最大边，而这也是所有可能路径里最小的最大边权——因为如果存在更小的最大边权，那Kruskal算法早就用更小的边把A和B连通了。

用你的例子验证 #

拿你给出的顶点A(0,0)、B(20,0)、C(5,5)、D(15,5)来说：

• 各边的长度（平方值，避免浮点误差）：AC=50，CD=100，BD=50，AB=400，AD=250，BC=250。
• 用Kruskal算法构建MST时，会先添加AC（50）、BD（50），然后添加CD（100）——此时A和B通过A→C→D→B连通，这条路径的最大边是CD的10，正好和你给出的最优结果一致。

实现注意事项 #

• 计算两点距离时，不需要开根号，直接比较距离的平方值即可，这样能避免浮点运算的误差，还能提高计算效率。
• 如果顶点数量很大（比如超过1000），Prim算法比Kruskal算法更适合完全图，因为Prim的O(V²)时间复杂度在稠密图上表现更好。

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