# Gas Station Problem - Dijkstra's Algorithm variation

## 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 :)

• Please do not vandalize your post if you cannot delete it. Even though you may have a solution now, we want to preserve the question and answers so that they can help others as well. – Discrete lizard Apr 14 '20 at 6:25

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