Can this be solved more efficiently than O(V * F + E)?

Revision en2, by quinoa, 2021-11-12 18:30:19

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. 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 a corresponding edge 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(V * F + E)$$$.

Is there a better solution?

Tags graphs, bfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English quinoa 2021-11-12 18:33:58 60
en3 English quinoa 2021-11-12 18:31:00 41 Tiny change: ' of fuel. ' -> ' of fuel. The car starts with a full tank of fuel. '
en2 English quinoa 2021-11-12 18:30:19 32 Tiny change: 'it of time. Some of ' -> 'it of time, and will burn $1$ unit of fuel. Some of '
en1 English quinoa 2021-11-12 18:29:33 1102 Initial revision (published)