提问人：user1171376 提问时间：6/11/2023 最后编辑：user1171376 更新时间：6/11/2023 访问量：114
计算加权无向图中节点 s 和 t 之间的瓶颈距离在 O（V+E） 时间内是否最多为 W 的算法
Algorithm to calculate if bottleneck distance between Nodes s and t in a weighted undirected graph is at most W in O(V+E) time
问：
我目前正在学习 Jeff Erickson 的《算法》一书第 270 页上的练习 9.b）
考虑两个顶点 s 和 t 之间的路径，在无向加权 图G。此路径的宽度是 路径。s 和 t 之间的瓶颈距离是最宽的宽度 从 s 到 t 的路径（如果没有从 s 到 t 的路径，则瓶颈距离 是−∞;另一方面，从 S 到自身的瓶颈距离为 ∞。
描述一种算法，用于在 O（V + E） 时间内解决以下问题： 给定一个无向加权图 G、两个顶点 s 和 t，以及 权重W，s和t之间的瓶颈距离最多是W吗？
我想我可以通过修改 Kruskal 算法在 O（ElogE） 时间内解决问题，首先找到一个最大生成树，然后使用 BFS 找到 s 和 t 之间的路径上的最小权重，但是我真的不明白如何在 O（E + V） 时间内解决这个问题。我试图以某种方式修改 BFS 算法，但没有任何运气。
我能够找到一个类似的问题，要求查找瓶颈距离是否至少为 W。这可以通过删除权重小于 W 的边并使用 BFS 检查 t 是否可以从 s 到达来轻松解决。不过，我不认为这个解决方案是直接适应的。 有什么提示吗？
答：
0赞
ravenspoint
6/11/2023
#1
请注意，系统不会要求您查找路径，只会在其宽度上设置上限。
如果 s 无法到达 t，则宽度为负无穷大 - 因此它小于 W。
您必须检查 s == t，这不会花费大量时间。
路径的宽度不能大于任何边的最大权重。遍历边缘，跟踪最大权重。将最大宽度与 W 进行比较，您就完成了。
0赞
Matt Timmermans
6/11/2023
#2
这个问题可以改写为“是否不可能使用权重大于 W 的边连接 s 和 t”
您已经知道如何运行 Kruskal 的算法，因此这对您来说很容易。无需对边缘进行排序。只需将所有权重为 > W 的边相加，看看 s 和 t 是否连接。或者 DFS/BFS 在具有这些边的子图上。
上一个：在回溯中记住列表
评论