Path with least maximum edge weight

Question

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

We have 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 the path contains.

Here's an example.

Graph with 4 nodes and 4 edges:

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

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

Dijkstra standard SSSP (reconstructing the path and finding the second highest edge) obviously doesn't work. I've thought at MST (which should be OK) but it's not guaranteed to cover the best path (u,v).

Answer 1

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-weight (as opposed to second max-weight) shortest path trees, one directed leafward from the root u, one directed rootward to the root v. For each edge s->t, consider the path consisting of the max-weight shortest path from u to s, the edge s->t, and the max-weight shortest path from t to v, whose second max-weight is bounded by taking the maximum of the u->s and t->v segments.

Answer 2

Consider binary search for the optimum cost. Sort weights of all edges, and search for the least value X satisfying the condition:

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

How to check the condition? For a given X:

1. Run DFS from u and find set U of vertices reachable from u using edges of weight at most X. If v is in U, condition is satisfied.

2. Otherwise find according set V with DFS from v.

3. The condition is satisfied if and only if there exist an edge with one vertex in U and other in V.

Time complexity: O(E log E).