### Thread: Shortest path (cost reduction algorithm)

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2010
Posts
4
Rep Power
0

#### Shortest path (cost reduction algorithm)

Hello ,
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 :
20 30
10 1000
0 3.459
5 1.789
6 1.879
10 1.929
103 1.129
213 1.459
512 1.349
731 1.789
816 1.449
934 1.999
35 20
1 100
0 5.000
0 0

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!

2. 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.
Code:
GOING        COMING
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
-------|------------|------
>------------^
Code:
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
---------------------------------Total---\$90.207
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2010
Posts
4
Rep Power
0
Originally Posted by requinix
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.
Code:
GOING        COMING
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
-------|------------|------
>------------^
Code:
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
---------------------------------Total---\$90.207

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?
4. Because
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.
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2010
Posts
4
Rep Power
0

#### Worked

Originally Posted by requinix
Because
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.
Hi requinix, i made the array to reflect gas stations from distance 1 to 2000 and it worked fine!!
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