如何在O(V+E)时间内判断s与t的瓶颈距离是否≤W？

首先明确核心等价关系：

s与t的瓶颈距离 ≤ W ⇨ 不存在任何s到t的路径，其路径宽度（路径中边的最小权重）> W

而路径宽度>W的充要条件是路径上所有边的权重都>W（因为路径宽度是路径里的最小边权，最小边权>W意味着所有边都>W）。

所以问题可以转化为：

• 构造子图G'：仅保留原图G中边权>W的所有边
• 用BFS或DFS（时间复杂度O(V+E)）判断s和t在G'中是否连通
  • 如果不连通：说明没有全边权>W的路径，即所有路径的最小边权≤W，因此瓶颈距离≤W，返回True
  • 如果连通：说明存在路径的最小边权>W，因此瓶颈距离>W，返回False

这个思路完全复用了你熟悉的“删边+BFS/DFS”框架，只是调整了保留边的条件——从保留≥W的边改成保留>W的边，通过判断连通性推导相反结论。

补充逻辑验证：

• 设瓶颈距离为B，B≤W等价于没有路径的min边权>W，也就是G'（边权>W的子图）中s和t不连通，逻辑自洽。
• 算法时间复杂度为O(V+E)：线性遍历所有边构造子图，加上BFS/DFS的线性时间开销。

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