带权有向图中s到t的线性时间最小瓶颈路径求解疑问

你的思路的时间复杂度问题 #

你的核心思路没问题——找最小的权值w，让s能通过权值≤w的边到达t，但原始实现方式会超时：

• 边权范围是1到|V|，最多有|V|个不同的权值档位。如果每次加完对应权值的边就重置所有顶点的访问状态，再用DFS/BFS从s遍历查t是否可达，最坏情况要跑|V|次全图遍历，总时间会到O(V² + E)，这显然不是线性时间（比如图是一条边权依次为1到|V|的有向链，每次都得遍历整个链才能确认t是否可达）。

改成线性时间的正确实现方式 #

只要优化可达性的维护方式，就能把时间压到线性，针对有向图的场景：

1. 先把所有边按权值分组，因为权值范围是1到|V|，直接用数组存每个权值对应的边列表，这一步是O(E)时间。
2. 初始化一个布尔数组reachable，只有reachable[s] = true，其他都是false。
3. 按权值从小到大遍历每个边组：
   • 遍历当前组的每条边(u→v)：如果reachable[u]为true且reachable[v]为false，就把reachable[v]设为true。
   • 处理完当前组的所有边后，检查reachable[t]是否为true。
   • 如果是，当前权值就是最小瓶颈，直接返回。
4. 如果遍历完所有权值都没找到，说明s到t没有路径。

• 这个方法的总时间是O(E+V)：每个顶点只会被标记为可达一次，每条边只会被检查一次，完全符合线性时间要求。

拓展：无向图的线性解法（参考） #

如果是无向图，用并查集会更高效：

1. 同样按权值分组边，O(E)时间。
2. 初始化并查集，每个顶点自己成一个集合。
3. 按权值从小到大遍历边组：
   • 对每条边(u,v)，把u和v所在的集合合并。
   • 每次合并后检查s和t是否在同一个集合里。
   • 若是，当前权值就是答案。

• 并查集的合并/查找操作近似O(1)，总时间也是O(E+V)。

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