gas station problem

[Fatema Zohora]

Some of you came to me regarding the assignment given on greedy algorithm. I am explaining the assignment again:

Input from user: 

1. Number of gas stations.
2. amount of gas available at each gas station (the max gas that you can take at any station)
3. Gas usage while going from station k to k+1 for   1 <= k <= n, where n=number of gas station 

 Output: A starting node/station 'v' such that starting from that station you can travel the whole circular path and get back to that starting node/station v 

as this is a greedy algorithm so you will be greedy and you don't want to take any risk. so what can you do? what will be the most greedy way to solve the problem? 

Note here, capacity of car is not given. So you can take as much gas as you want. You are also not asked to minimize the total amount of gas taken. You are just asked to find out a cycle that starts at a gas station and after traveling the cycle returns to that same gas station. But you need to find out that path doing as less calculation as possible. Because you want to be efficient. so you want to design a faster way to solve the problem/find out that path. 

lets think number of gas station is 7. User will have to input gas amount at each of those 7 stations. then input gas usage while going from 1 to 2, 2 to 3, 3 to 4, 4 to 5, 5 to 6, 6 to 7, 7 to 1. (circular path) 

Greedy strategy:   Start testing from first station. You have to check if you can get back to that station after traveling the whole circle. while travelling, at each gas station, just take all the gas as you are greedy. Now if you got stuck while going from station k to k+1. lets say, your car's gas is exhausted while going from 3th to 4th gas station. Then start the test again from station k+1 that is 4th station. That means you have to consider 4th station as starting point. Then again continue the journey to see if its possible to get back to that starting station (k+1) which is 4 in this case. 

Now, while doing this testing about which should be the starting point, if you see that you have crossed the 1st station (after testing other nodes on that circular path as starting node) but still you haven't found a node such that starting from that node, you can travel the circle and get back to that node, then it will mean No Such Path exists. So then just print that according to users given input, no such path exists. But if you can find a path like that, then just print the corresponding starting node/station.

I will upload an example soon. 

[Moin Mostakim]

I hope this explanation is clear to you all. Hope to see your program
in next class.

Thanking You

Moin Mostakim

On 3/25/13, Fatema Zohora <anne....@gmail.com> wrote:
> Some of you came to me regarding the assignment given on greedy algorithm.
> I am explaining the assignment again:
>
> Input from user:
>

> 1. Number of gas stations.
> 2. amount of gas available at each gas station (the max gas that you can
> take at any station)
> 3. Gas usage while going from station k to k+1 for 1 <= k <= n, where

> --
> You received this message because you are subscribed to the Google Groups
> "Dashboardalgorithm" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to dashboardalgori...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>