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