Gas Station Problem - Dijkstra's Algorithm variation

Question

I am trying to find an algorithm which finds the least expensive route from one town to another.

This is the general setup.

There are a series of one-way roads from some towns to other towns. Not all towns have roads between them. Let R be the set of all the roads and let T be the set of all towns. For two towns u, v ∈ T, let (u→v)∈ R be the one-way road from u to v and let w(u, v) be the amount of gasoline required to travel along this road.

Let S ⊂ T be the set of towns which have gas stations. At a town u ∈ S, one can choose to pay c(u) dollars to fill up the gas tank. Note that the cost does not change depending on how much gas must be bought; if you need to buy gas, fill up the whole tank. The cost is only affected by which town u is.

The car’s tank can hold k units of gas and it is full at the start.

My ideas:

I believe this uses a shortest path graph algorithm, but I am unsure how to implement it. I believe it uses Dijkstra's algorithm. I also recognize that the run-time depends on |T|, |R| and |S|.

Any advice will help! thanks :)

Answer 1

We note that we can assume that the source node has a gas station with refilling cost as $0$, even if it doesn't. It just makes the algorithm cleaner, as we start out with a full tank, and we note that no optimal solution is ever going to come back to the source again and refill. Similarly, we also assume that the $\text{target}$ also has a gas station with some arbitrary cost of refilling - the cost here wouldn't matter. So in effect, we set $S = S \cup \{\text{source, target}\}$.

In the first phase of the algorithm, for every $s \in S$, we want to find all the other towns in $S$ that we can reach without refueling, if we start out with a full tank from $s$. For this, we can take two approaches:

1. Run Floyd–Warshall using $w(u, v)$ as the weight of every edge, to find the shortest distance from any town to any other. Now, for every $s \in S$, we iterate through every other $t \in S$ and if the shortest distance from $s$ to $t$ is $\leq k$, then we can reach $t$ from $s$ without refueling. So we create a new graph $G'$, whose vertex set is $S$, and add a directed edge $(s, t)$ with a weight of $c(s)$. This approach takes $\mathcal{O}(|T|^3)$ time and $\mathcal{O}(|T|^2)$ space.
2. Another way to construct the same $G'$, would be to start a Dijkstra's from every $s \in S$, and stop when the distance is more than $k$, which in the worst case wouldn't help our complexity. This approach would require $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.

The second approach is asymptotically better than the first one, but the first one is easier to implement. So you can decide which fits your needs better.

Now on to the second phase of the algorithm, where we have the graph $G'$ with us, which again is a directed weight graph, but now the weights are costs of refilling. So all we have to do is run a Dijkstra's on this graph starting from $\text{source}$. The answer is the shortest distance to $\text{target}$.

So the total algorithm needs $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.