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

Here is my solution to the problem

The main objective is to change the cost of the all the routes to the costliest route's cost. In the above example the costliest route is 1-3-2-4 with cost 12. For every other than 1-3-2-4, traverse from the end and try to adjust the fees of the current road. You can do this only if this road is connected by one road, in other words the IN-DEGREE of this road has to be 1. If this road has in-degree more than 1 then traverse back to the previous road in this route and repeat the check. If you cannot find any road with in degree 1 then exit with no solution.

Adjusting the fee of a road is simply done by adding the {cost difference between the costliest route & this route} to this road's fee.

Algorithm

1. Find the costliest route available with us and lets call it as X;
2. Y = ROUTE_COST(X);
3. For (every route other than X) as A
  Begin
4.    R = the last road in this route A;
5.    while (R<>NULL && IN_DEGREE(R) > 1)
     Begin
6.        N = the Previous road connecting to the road R in this route A;
7.        R = N;
     End;

8.    if (R===NULL) then exit with "No Solution";

9.    C = ROUTE_COST(A);
10.  ROAD_FEES(R) = ROAD_FEES(R) + (Y-C);
  End;

Let me know if you see any issues.