我在一个项目上工作，并有一个问题，有关寻找从s到t在有向无环图的最大瓶颈路径。问题如下:
定义图中从s到t路径的瓶颈为该路径中边的容量中最小的容量。是否有可能在O(|E|)时间内找到一条从s到t且瓶颈容量最大的路径，其中|E|为图中的边数?我怎么做这样一个算法呢?
您可以从节点s开始对t进行广度优先搜索。因为你的图是无环的，这个搜索保证结束，或者返回从s到t的所有路径，或者没有路径，如果没有这样的路径。
- 在搜索时跟踪所有路径及其瓶颈。
- 当你到达一个中间节点
x时，该节点已经通过其他路径访问过，检查s -> x中哪条已知路径的瓶颈最高，并只保留那条。 - 同样也适用于
t，即如果你到达t，检查你是否已经找到任何其他路径到t，只保留最大瓶颈的路径。 - 一旦搜索结束，只有具有最大瓶颈的路径将保留(如果存在)
由于该方法最多访问每条边一次，因此它位于O(|E|)