minimum bottleneck path from s to t with 1 =<w(v) =< |V|

Question

given a directed graph G(V,E) with weights , all weights have the value of 1 to |V| , given two vertices s and t find minimum bottleneck path from s to t in linear time .

my idea is to add edges gradualy according to its weights first add edges with weight equal to 1 if there is a path from s to t return 1 as the min bottleneck else add all edges with weight 2 and according to the edge itself change the visited vertices to unvisited .

i am not sure if the solution above is linear . any ideas ? thank you

Answer 1

1. Because all the weights are in [1,|V|], you can sort the edges by weight in linear time.

2. Then, clear all edges from the graph and start adding them back in weight order, stopping when vertex t becomes reachable from vertex s.

3. At this point, the graph will include a minimum bottleneck path, and no edges will be more expensive that the bottleneck. You can do a BFS in this graph to find the path.

In order to make this a linear time algorithm, you need to do step (2) in linear time, and for that you need to track which vertices are reachable from s in amortized constant time per edge. The trick is to process each edge for reachability just once:

• When you add an edge from a reachable vertex, its target becomes reachable immediately.
• Otherwise, it goes into a queue for that vertex, and all the edges in that queue will be processed when their source becomes reachable, making all of their targets reachable at the same time.