Saturday, May 9, 2009

Toll fee Balancer

Came across an interesting Graph based problem. Try solving the problem, I will post my solution soon

In city to travel from a point A to B there are multiple routes, there can be direct route from A->B and there can few other routes with one or more intermediate nodes like A->C->B or A->C->D->B etc. Each road connecting two points have a cost, so any vehicle using that road should pay that cost to the authorities. This now implies that traveling from A to B will have different costs based on the route that you take.

Let me take an example

In the above figure Node '1' is the starting point and '4' is the ending point and there are 3 different routes to connect 1 and 4, each road has a original cost marked in BLUE. So the cost taking the direct road from 1-4 is 10, whereas taking the path 1-3-4 is just 8 (because 1-3 is 5 and 3-4 is 3), similarly the cost of taking the 3rd route 1-3-2-4 is 12.

Now the problem is to reassign the cost of individual roads so that the cost of all possible routes remains the same. You cannot reduce the cost of a road, but you can increase it. In the above example the cost of road 1->4 and 3->4 is reassigned and the extra cost for these roads are marked in RED. Now taking any of the routes will cost the same amount 12.

Note: There can be few cases with no solution too.

Solution >>>