0

我正在做一个项目，并且遇到与在有向无环图中找到从s到t的最大瓶颈路径有关的问题。问题如下：

将图中从s到t的路径的瓶颈定义为路径中边容量中的最小容量。是否有可能在O(|E|)时间内找到一条从s到t的具有最大瓶颈容量的路径，其中|E| 是图中的边数？我将如何制作这样的算法？

4

1 回答 1

0

t您可以从 node 开始进行广度优先搜索s。由于您的图表是非循环的，因此此搜索保证会结束，如果没有这样的路径，则返回所有来自sto 的路径或不返回任何路径。t

  • 在搜索时跟踪所有路径及其瓶颈。
  • x当您到达一个已经通过其他路径访问过的中间节点时，检查哪条已知路径s -> x的瓶颈最高，并只保留那个。
  • 这同样适用于t，即如果您到达t，请检查您是否已经找到任何其他路径t并仅保留具有最大瓶颈的路径。
  • 搜索结束后，仅保留最大瓶颈的路径（如果有的话）

由于这种方法最多访问每个边一次，它在O(|E|)

于 2021-09-25T14:31:52.050 回答