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.
Best Answer
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.