Give an $O(n^3)$-time dynamic programming algorithm for the given problem

Question

There are n cities in a country.

Every two cities u and v are connected by a bi-directional highway that takes $l(u,v)$ hours to drive through.

A car with gas tank capacity $c$ can only travel for $c$ hours on a highway and has to be refuelled at the cities.

Give an $O(n^3)$-time dynamic programming algorithm to compute, simultaneously for all pairs $(u,v)$ of cities, the minimum gas tank capacity needed to go from $u$ to $v$.

Can someone give me a direction/hint as to how to solve this question? Any explanation would be really appreciated.

Answer 1

Are you familiar with Dijkstra's Algorithm to find the shortest path to each node in a graph? This is essentially going to be the same thing except when you update paths between nodes, you want to throw out cases when $l(a,b)$ is more than $c$. So in Dijkstra's algorithm, you start by putting infinity everywhere except for the source node, and then at each step you update adjacent vertices with the current shortest path from a nearby vertex plus the cost of moving to that vertex. Again, if you see that $l(a,b)>c$ you don't want to update that vertex. Once the algorithm terminates you'll have the shortest path from the source node to every other node (note that some nodes may be unreachable if there doesn't exist a path satisfying $l(a,b)$ for each edge of the path). To get the minimum cost between any two nodes, subtract the costs with respect to the source vertex (this needs some simple justification). One thing that worries me is that Dijkstra is something like $O(n\log n)$, but to then get the minimum cost between any pair of cities is $\binom{n}{2}=O(n^2)$, so you're getting $O(n^3\log n)$. Perhaps someone smarter than me can comment on this.

Answer 2

Figuring out how to use dynamic programming in particular for this problem and stay within $O(n^3)$ took me some time. In the mean time here's a somewhat straightforward $O(n^2 \log n)$-time algorithm:

Start by sorting a list of all the edges by their length. For $O(n^2)$ edges this takes time $O(n^2 \log(n^2))=O(n^2 \log n)$ and will turn out dominate the running time.

Now maintain a union-find structure where each node is initially a singleton set, and consider the edges with the shortest ones first. Whenever you see an edge connecting two nodes that haven't been unified yet, you know that the length of that edge will be the critical one between any city in one subset and any city in the other subset -- so at that point you can fill the result in for all of those cities. Then unify the two subsets and continue looking at longer edges.

There's plenty of time for the union-find operations themselves within $O(n^2 \log n)$ -- the standard path-compression implementation takes $O(\alpha(n))$ amortized time for each of the $n^2$ queries/updates we need to make.

Whenever we unify two sets we need to compute their cartesian product in order to update that many results, which looks like it could be expensive. However, every (unordered) pair of cities is in exactly one of these cartesian products, and we can compute each relevant cartesian product in time linear in its size, if only we have a list containing the members of each subset. The union-find structure doesn't give us such a list out of the box, but it is trivial to additionally maintain each subset of a doubly-linked circular list -- these lists can be spliced together in constant time whenever we unify two different subsets.

(And as soon as we do that, we don't really need the fancy union-find implementation after all, because we have time to update a subset identifier for each of the cities when we're touching it anyway in order to enumerate the cartesian product).

Answer 3

Ah, here's the dynamic-programming solution that was probably intended. Hint:

Suppose you have already tabulated the results for a country with $n$ cities, and then someone founds an $(n+1)$th one. Can we update our previous knowledge to cover the new situation in $O(n^2)$ time? Yes, if we do it in two phases:

• First find the capacity we need to go from the new city to each of the old ones.
• Then, for each pair of old cities, check whether it would improve the previous requirement to visit the new city when going between them.