# Find the minimal tank capacity to be able to travel from any city to any other

There are $$n$$ cities in the country. The car can go from any city $$u$$ to city $$v$$, On this road it spends $$w_{u,v} > 0$$ fuel. At the same $$w_{u,v}$$ can differ from $$w_{v, u}$$. The task is to find the minimal tank capacity to be able to travel from any city to any other (possibly with refuels) in $$O(n^2\log n)$$.

• What do you mean by refuels? – Yuval Filmus Oct 14 '19 at 15:00
• @YuvalFilmus Fuel can be added to the tank in some intermediate city. For example, the car travels from $A$ to $C$. It is possible to add fuel in the $B$. – user13 Oct 14 '19 at 15:37
• In that case, the answer is simply $\max(w_{u,v})$. This is an $O(n^2)$ algorithm. – Yuval Filmus Oct 14 '19 at 17:05
• @YuvalFilmus No, why? For example, the car can go from $A$ to $B$ it costs $1$ fuel, from $A$ to $C$ - $6$ and from $B$ to $C$ - 3. He can manage to go all the cities with $1+3$ fuel by traveling from $A$ first $B$ then $C$. Actually, I am not sure wheater the car then after $C$ should be able to drive back to $A$ or $B$. If so than it is fully connected graph. In this case maybe you are right. – user13 Oct 14 '19 at 17:11
• You simply refuel as you go. At each city fill the tank enough to last until the next city. The airline industry works this way. – Yuval Filmus Oct 14 '19 at 17:13

As long as |E|<<|V|^2 or the graph is not dense, your complexity constraint should be satisifed.
Johnson's algorithm does it in O(|V|^2 log |V|+|V||E|).
We first sort all edges according to their costs from small to large. Say the sorted edges are $$e_1,e_2,\ldots,e_{n(n-1)}$$, and the corresponding costs are $$w_1\le w_2\le\cdots\le w_{n(n-1)}$$. Then we find the minimal $$i$$ such that the graph is strongly connected only with the edges $$e_1,\ldots,e_i$$. Now $$w_i$$ is the minimal tank capacity we want.
Sorting costs $$O(n^2\log n)$$ time. To find the minimal $$i$$, we can use the bisection method. We first test whether the graph is strongly connected with the edges $$e_1,\ldots,e_{n(n-1)/2}$$. If yes, we then test the connectivity with the edges $$e_1,\ldots,e_{\lceil n(n-1)/4\rceil}$$, otherwise we test the connectivity with the edges $$e_1,\ldots,e_{\lceil3n(n-1)/4\rceil}$$, and so on. The running time to find the minimal $$i$$ is also $$O(n^2\log n)$$. So the total running time of this algorithm is $$O(n^2\log n)$$.