0

I am working on a project and have a problem relating to finding a maximum bottleneck path from s to t in a directed acyclic graph. The problem is as follows:

Define the bottleneck of a path from s to t in a graph to be the smallest capacity out of the capacities of the edges in the path. Is it possible to find a path from s to t with the maximum bottleneck capacity in O(|E|) time, where |E| is the number of edges in the graph? How would I make such an algorithm?

tinyline
  • 9
  • 1
  • Welcome to Stack Overflow. Please take the [tour] to learn how Stack Overflow works and read [ask] on how to improve the quality of your question. Then check the [help/on-topic] to see what questions you can ask. Please see: [Why is “Is it possible to…” a poorly worded question?](https://softwareengineering.meta.stackexchange.com/q/7273) (don't just change your question to "How"). Please see: [How do I ask and answer homework questions?](https://meta.stackoverflow.com/q/334822) Please show your attempts you have tried and the problems/error messages you get from your attempts. – Progman Sep 25 '21 at 14:11

1 Answers1

0

You can do a breadth-first search for t starting at node s. As your graph is acyclic, this search is guaranteed to end, either returning all paths from s to t or no paths, if there is none such path.

  • While searching keep track of all paths and their bottlenecks.
  • When you reach an intermediate node x which was already visited via some other path, check, which of the known paths from s -> x has the highest bottleneck and keep only that one.
  • The same also applies for t, ie if you reach t, check if you already have found any other path to t and keep only the path with the maximum bottleneck.
  • Once the search has ended, only the path with the maximum bottleneck will remain (if there is any)

As this approach visits each edge at most once, it's in O(|E|)

derpirscher
  • 14,418
  • 3
  • 18
  • 35