April 4th, 2010, 11:59 AM
Shortest path (cost reduction algorithm)
I have come across a problem,which states as follows :
I have tried a lot to get the right answer, but i am not able to
Intro: We will be renting a van and driving somewhere in the southeast.We have very little money to work with and want to make the trip as inexpensive as possible.Figuring out the best route is easy - but what about the price of gas? There may be many gas stations along the way, with different prices. How can we minimize the cost?
Problem: Given a description of the van and the route, compute the smallest amount of money possible to spend on gas. Whenever we stop for gas we always fill the tank entirely. It might be cheaper to put in gas only to get to the next cheapest gas station, but we wont do that - thats WAY too COMPLEX.
Remember, we have got to go to the destination and come back! The amount has to be for the round trip.Assume that we do not do any driving at the destination point.Assume that we take the same route back, just in the other direction. There will always be a station at mile 0. This is the rental agency and they insist that we fill our tank when we return the van. Assume that the tank starts out at full.
The input :
There will be one or more input sets. Each set will begin with a line describing the van. it will have 2 positive integers :
tank mpg (1<=tank<=100 and 1<=mpg<=100)
which denotes the size of the van's tank in gallons, and the van's fuel efficiency in miles-per-gallon respectively.
The next line describes the route. It has two integers :
n miles (1<=n<=10000 and 1<=miles<=5000)
which denote the number of gas stations along the way, and the length of the trip, one way, in miles.
The next line n describes the gas stations, one per line. They each contain an integer and a real number.
distance cost (0<=distance<=miles , 0.000 <=cost<=100.00)
which represent the distance in miles from the beginning of the trip to this gas station, the cost in dollars of a gallon of gas here. There will always be a station at distance 0(the rental agency). When the van is returned, the tank must be filled at this station. The stations are guaranteed to be listed in nondecreasing order of distance. There is guaranteed to be a solution.
The input will end with an empty input set, with tank=mpg=0. Don't process this set.
The Output: For each input set, print the number starting with 1 and produce a single real number on its own line, with exactly two decimal places, representing the least amount in dollars and cents that gas my cost on this trip. Do not print any blank lines, Round to the nearest penny.
Sample input :
Sample output(corresponding to sample input):
Trip 1: 90.21
Trip 2: 50.00
NOW, HERE IS THE APPROACH I TOOK :
I want to apply Dijkstra's shortest path algorithm to solve this.
My biggest problem has been - how to create the graph and how to assign weights of the edges.
I created a graph with the starting point, all the gas stations along the way and the destination as nodes.
The weights were assigned by : (distance between this node and previous node) * (cost of gas at previous station)/mileage;
After applying Dijkstra algorithm from source to destination, I got a cost of 43.57, i thought since the return route is the same, just multiply by 2.
But i am not getting the answer of 90.21
Can someone please give me the shortest path and help me find out how do we reach the 90.21 figure? I dont quite understand what i am mising here.
Is my approach to the solution wrong (something wrong in creating the graph)?
It would be really great if someone could help me on this!
April 4th, 2010, 03:09 PM
1) Dijkstra's isn't really for this
2) The cost of a "line" depends on the destination, not the source
3) The two paths are not the same
Starting at the source (0mi) you can go a maximum of 20gal*30mpg = 600 miles before you have to refill the tank. So somewhere in there you refill: naturally, at the cheapest place. Then you have refill within another 600 miles, then again and again and again until you're back home.
Miles V Cost ^ Miles
0 | $3.459 X 1000
5 | $1.789 X 995
6 | $1.879 | 994
10 | $1.929 | 990
103 X $1.129 X 897
213 | $1.459 | 787
512 X $1.349 X 488
731 | $1.789 | 269
816 X $1.449 X 184
934 | $1.999 | 66
Range Station Price Dist. Cost
0-600mi 103mi $1.129 103mi $ 3.876
103-703mi 512mi $1.349 409mi $18.391
512-1112mi 816mi $1.449 304mi $14.683
816-1416mi 1184mi $1.449 368mi $17.774
1184-1784mi 1488mi $1.349 304mi $13.670
1488-2000mi 1897mi $1.129 409mi $15.392
1897-2000mi 1995mi $1.789 98mi $ 5.844
1995-2000mi 2000mi $3.459 5mi $ 0.577
April 4th, 2010, 05:00 PM
Originally Posted by requinix
Hello requiunix, thank you for explaining it to me!!
I really appreciate it.
If Dijkstra isnt the algorithm for this, then which one is? Why cant I apply Dijkstra here?
April 4th, 2010, 05:42 PM
a) The cost of a path between two nodes depends on an unknown, future destination
b) It's less efficient than a simple linear approach
With that said, you could probably modify Dijkstra's to fit this task (such as doing the math backwards to counter (a)) but that's not nearly the first thing I thought of given the problem.
April 4th, 2010, 06:30 PM
Hi requinix, i made the array to reflect gas stations from distance 1 to 2000 and it worked fine!!
Originally Posted by requinix
So the solution is to create the nodes for the entire trip, and not just one way and to have the cost as the cost of next gas station.
Thanks requinix for helping me out!! I really appreciate it