求源点到目标点所有路径的最小最大边权值，寻求优化算法

给定带权图，需找出从源点到目标点的所有路径中，各路径最大边权值的最小值。例如示例中节点1到6有两条路径：上方路径最大边权为4，下方为6，答案取4。原采用DFS遍历所有路径的方法时间复杂度为O(v^v)（指数级），需更优算法。

1. 修改版Dijkstra算法 #

这是单源单目标场景下最直接的高效解法：

• 核心逻辑：将标准Dijkstra算法中「路径总权和最小」的优化目标，替换为「路径上最大边权的最小值」。
• 实现步骤：
  • 维护数组dist[]，其中dist[u]表示从源点到节点u的路径中，最大边权的最小值。初始时源点dist[src] = 0，其余节点设为无穷大。
  • 使用小顶堆（优先队列），每次取出当前dist值最小的节点u。
  • 遍历u的所有邻边(u, v)，边权为w。计算候选值max(dist[u], w)，若该值小于dist[v]，则更新dist[v]并将v加入优先队列。
  • 当目标点被从堆中取出时，dist[dst]即为所求答案。
• 时间复杂度：O(M log N)，其中N为节点数，M为边数，远优于指数级复杂度。

2. 二分查找+BFS/DFS #

适合边权范围明确的场景：

• 核心逻辑：通过二分枚举可能的最大边权值，判断是否存在一条所有边权均≤该值的路径，连通源点与目标点。
• 实现步骤：
  • 确定所有边权的范围[min_w, max_w]，作为二分的左右边界。
  • 取中间值mid，构造子图：仅保留边权≤mid的边。
  • 用BFS或DFS判断子图中源点与目标点是否连通。
  • 若连通，说明可以尝试更小的最大值，调整右边界为mid；若不连通，调整左边界为mid + 1。
  • 最终收敛的边界值即为答案。
• 时间复杂度：O((N+M) log max_w)，其中max_w为图中最大边权。

3. 最小生成树（Kruskal/Prim算法） #

利用最小生成树的性质快速求解，尤其适合多组源-目标查询的场景：

• 核心逻辑：源点到目标点在最小生成树上的路径，就是所有路径中最大边权最小的那条路径。
• 实现步骤：
  • Kruskal方式：将所有边按权值从小到大排序，依次加入生成树，当源点与目标点首次连通时，当前加入的边的权值就是答案。
  • Prim方式：构建完整的最小生成树后，在生成树上查找源点到目标点的路径，取路径中的最大边权即为答案。
• 时间复杂度：Kruskal算法为O(M log M)，Prim算法（斐波那契堆实现）为O(M + N log N)。

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