1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ What do you mean by refuels? $\endgroup$ – Yuval Filmus Oct 14 at 15:00
  • $\begingroup$ @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$. $\endgroup$ – user13 Oct 14 at 15:37
  • $\begingroup$ In that case, the answer is simply $\max(w_{u,v})$. This is an $O(n^2)$ algorithm. $\endgroup$ – Yuval Filmus Oct 14 at 17:05
  • $\begingroup$ @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. $\endgroup$ – user13 Oct 14 at 17:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 14 at 17:13
1
$\begingroup$

A possible solution may be to compute the all pair shortest path matrix and then select the largest value in the matrix.

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|).

Refer to this for a better understanding of time complexity in case of Jhonson's Algorithm.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.