Clever Geek Handbook

Path with the lowest maximum edge weight

Let's say we have a directed non-negative weighted graph.

We need to find the least cost path between (u, v). The cost of a path is defined as the maximum cost of the second most expensive edge that contains the path.

Here's an example.

Graph with 4 nodes and 4 edges:

  • from 1 to 2 at a cost of 3
  • from 1 to 3 at a cost of 7
  • from 2 to 3 at a cost of 5
  • from 3 to 4 at a cost of 2

The optimal path between 1 and 4 should be 1 - 3 - 4 with a total cost of 2 (costs 2 and 7, second highest is 2).

Dijkstra's standard SSSP (Path Reconstruction and Second Highest Edge Search) obviously does not work. I thought it was in MST (which should be good), but it is not guaranteed to cover the best path (u, v).

+3


source to share


3 answers


You can do binary search on the answer (sort the edges by their weight before it).
For a fixed answer c, let weights> c heavy and other edges of the world.
So, all you need to check is a path with at most 1 heavy edge. You can do this by assigning 0 values ​​to the light edges and 1 to the heavy ones and doing 0-1 bits. If the distance is <= 1, then you can get a path with a cost of at most c. Time complexity - O (E log E).



+2


source


We can get O (E + V log V), which is o (E log E) for sufficiently dense graphs. Using Dijkstra with a Fibonacci heap, compute two max-weights (as opposed to the second max-weights) of the shortest path trees, one directed from the root u, one directed by the root to the root v. For each edge s-> t, consider a path consisting of a shortest path of maximum weight from u to s, an edge s-> t and a shortest path of maximum weight from t to v, the second maximum weight of which is bounded by the maximum value u-> s and t- > v segments.



+2


source


Consider a binary best value search. Sorting the weights of all edges and finding the smallest value X

that satisfies the condition:

There is a u -> v path which has at most one edge with weight greater than X.

How to check the status? For a given X

:

  • Run DFS from u

    and find the set of u

    vertices reachable u

    from using edge weights at most X

    . If v

    found u

    , the condition is met.

  • If not, find the matching set v

    with DFS from v

    .

  • The condition is satisfied if and only if there is an edge with one vertex at u

    and another at v

    .

The complexity of time: O(E log E)

.

+1


source






More articles:


All Articles