1
$\begingroup$

I am trying to solve one problem. Please refer complete problem statement before proceeding.

You are given a road network, with N cities and M bi-directional roads. Each road has some positive amount of tax associated to it,meaning if there is a road connecting cities A and B with tax C, you will need to pay C rupees to the government every time when you use this road.

but you have a wildcard which can be used at most K times and when you use wildcard while using a road, you do not need to pay tax associated with the road.

You are planning to visit one city this weekend, due to limited budged you want to estimate minimum passible cost from you home-city to every other city, so that you can choose the destination according to the budget, your home-city is a city numbered with 1.

For solving above problem I am Following this approach. Step 1) Calculate all the path between vertices u,v. Step 2) For a Path p=[i-j-k-l] do following

   for(int i=0;i<k;i++){
           int weight=findEdgeWithMaxWeight(p);
     cost of path p=cost of path-weight;
    }

I am repeating this step2 for all the paths for u,v and at last I am choosing the path with minimum weight. As my answer.

Consider following diagram to visualize my approach.

enter image description here

But problem with above approach is that I am have to calulate all the path between u,v to get the answer. Is there any way to get the optimal path with out calculating all the paths?

Edit: Hope Problem is bit clearer now.

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
1
$\begingroup$

One way to solve this is a Dijkstra variant with the following DP-Relaxation:
The distance array will be 2-dimensional array for which $Dist[i][j]$ is the shortest path from the source to the city $i$ using $j$ wildcards.
When processing a vertex $i$, for an incident edge $e\{i, j\}$ with cost $c$ we update as following:(for all values of k)
$Dist[j][k] = min(Dist[j][k], Dist[i][k] + C)$
$Dist[j][k] = min(Dist[j][k], Dist[i][k-1])$ The correctness follows from the fact that we are trying all placements of the wildcards and keeping the so-far-optimal.
The runtime is the usual Dijkstra runtime multiplied by the $K$ factor in the relaxation i.e. $O((e+n\log(n))k)$ using Fibonacci Heaps.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Dist[j][k]=min(Dist[j][k],Dist[i][k]+C)??? you are calculating Dist[j][k] with the help of Dist[j][k] itself? I mean is it correct? $\endgroup$
    – Thinker
    Jan 8, 2019 at 18:38
  • $\begingroup$ What exactly is happening? Are you running dijkstra K time from 1 to K and updaing the matrix as per the above equation? And please confirm "Dist[j][k]=min(Dist[j][k],Dist[i][k]+C)" this equation. $\endgroup$
    – Thinker
    Jan 8, 2019 at 18:54
  • $\begingroup$ The equation means update dist[i][k] if the new value is smaller $\endgroup$
    – Narek Bojikian
    Jan 9, 2019 at 0:07
  • $\begingroup$ You can consider it as K dijkstras but they all run at the same time so you calculate for each node how much does it cost to reach that node starting from the source and using k cards which is coming to some previous node using k cards and then coming to this one paying for the edge or comig to the previous one using k-1 cards and using one addition card for the edge $\endgroup$
    – Narek Bojikian
    Jan 9, 2019 at 0:10
  • $\begingroup$ The second equation d[j][k+1]=min( d[j][k], d[i][k-1]) should not it be d[j][k] instead of d[j][k+1] ??? $\endgroup$
    – Thinker
    Jan 13, 2019 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.