Path with least max-weight, in an undirected connected graph

Question

The problem we were given, states that we have graph, where vertices are cities, and edges are roads. Each edge has a weight equal to the kilometers of the corresponding road. We want to get from city $A$ to city $B$, with a car that can last up to $M$ kilometers in one go, but we can refuel, every time we go to a city. It isn't mentioned, but i guess we can't suppose that the graph is acyclic, since it represents a country's map.

We need to find two algorithms that give as the least $M$ our car needs to have to get from a city $A$ to city $B$. One should have time complexity $m\log m$, and the other one linear (where $m$ is the number of edges).

I thought that we could use BFS/DFS for that, but they aren't what we are looking for, because of the complexity. The only other thing I came up with is using Kruskal algorithm somehow, because it has the complexity we want, and also the graph is connected, so maybe we have less things to worry about. As for the linear one, I can't find anything.

Answer 1

This problem is known as the minimax path problem. A linear time algorithm is given in this note. I quote it here. Note the note solves the bottleneck shortest path problem, and to solve your original minimax path problem, you should reverse the sense of all the weight comparisons performed by the algorithm, or equivalently replace every edge weight by its negation.

The correctness of Algorithm 1 (for undirected graphs) is rather obvious: If in line 6 it turns out that the graph still is $s$–$t$–connected, than hiding the edges of weights less than $M$ in line 5 did not affect the optimal solution. Otherwise, in each subgraph to be shrunken in line 9, every vertex can be connected to every other one by a path with capacity at least $M$; thus the bottleneck of $t$ (being smaller than $M$) will remain the same in the shrunken graph.

Furthermore, the algorithm runs in time $O(m)$, where $m = |E|$ denotes the number of edges: The crucial observation is that in every iteration of the loop in lines 3–11 half of the edges are removed from the graph, either by shrinking all "thick" edges (in line 9) or by dropping all "thin" edges (in line 5). As all steps inside that loop can be done in linear time in the size of the current graph, the total running time is bounded by $$O(m)+O\left(\frac{m}{2}\right)+O\left(\frac{m}{4}\right)+\cdots=O(m).$$ This shows the following result.

Answer 2

Please check whether $m$ is the number of edges. If the graph is complete, we need at least $O(m^2)$ time just for reading weights of all edges.

Anyway, Kruskal looks like the right algorithm to think about.

We need to find the first $M$ such $A$ and $B$ will belong to the same component in the graph induced by the set of edges with weights $\le M$. It means that we can check this condition after each Kruskal' iteration, and when it holds at the first time, weight of the last edge will be an answer.

If we use, e.g., DSU for the implementation, we will have complexity $O(E \log E)$, where $E$ is the number of edges.

If the set of edges is already sorted, we get $O(E \cdot{} \alpha(m))$. If not, I don't think that a linear algorithm exists, because intuitively it should be not easier than sorting.