quinoa's blog

By quinoa, history, 3 years ago, In English

Problem statement

A car is traveling in a directed graph from point $$$A$$$ to point $$$B$$$. Its fuel tank has a capacity of $$$F$$$. Traveling along an edge takes $$$1$$$ unit of time, and will burn $$$1$$$ unit of fuel. The car starts with a full tank of fuel. Some of the vertices in the graph are gas stations where the car can refuel. Refueling takes $$$1$$$ unit of time. What is the minimum time to travel from $$$A$$$ to $$$B$$$ (if it is possible at all)?

Original link to the problem

The best I can come up with

Make a new graph where every vertex is a combination of the vertex in the original graph, and the remaining fuel in the tank: $$$vertex_{new-graph} = (vertex, fuel)$$$. For every edge in the original graph, add corresponding edges in the new graph. If the original vertex is a gas station then we have to add 2 edges (one corresponding to refueling, and one corresponding to not refueling). We can now do a BFS which will take $$$O(V_{new-graph} + E_{new-graph})$$$ time which equals $$$O(F * (V + E))$$$.

Is there a better solution?

Edit: I messed up the time complexity.

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

You may notice that F' = min(F, V), as we will never require any more than V-1 fuel units. So O(V*(V+E))