CODEWITHSUNDEEP
arraysalgorithmgraphdynamic-programming
Ilan Aizelman WS
Ilan Aizelman WS

Reputation: 1632

Given two paid roads from point x to point y, find the cheapest road

Given: Two roads, L and R, they both start from point x and end in point y.

They're both paid roads, and they have n paid points in the road l1,l2,..,ln on the L road and r1,r2,...rn on the R road, which you have to pay when you cross that point.

If you want to keep driving to point y from R road instead of L (or from road L instead of R), you have to pay the changing road fee(but not the paid point).Meaning, If you leave in point i, you don't have to pay for the point li or ri, but just the changing road fee, and then you continue to the i+1 point in the new road you're in (R or L) - and you have to paid that l(i+1) or r(i+1). points of changing road fee are defined by s1,s2,...sn.

EXAMPLE: If I'm in point 3 in road R and I choose to keep driving to point y from road L, I just pay s3 (and not r3), and then I pay l4 too.

Question: Solve this in DP that finds the cheapest way from x to y with the best time complexity.

I come up with a solution which I believe won't work all the time, and I hope you can help me construct a better working one.

Define: Graph G, 2n vertices, edges are (li, li+1), (li, ri), and even 3n vertices because of (ri,ri+1). Array of size n called x. so x[i] will hold the value of the lowest cost route on up to index i. We will fill the array from the n to 1. We'll init the values of the array with zero. And the formula be as followed. A[i] = min { A[i+1] + xi, A[i+1] + si + x_(i+1)] }. In the end, we return A[1].

I believe this fails sometimes, If it's true, I would love to get some help on changing it to work properly or finding another algorithm that will get this job done.

Upvotes: 0

Views: 82

Answers (1)

Tobias Ribizel
Tobias Ribizel

Reputation: 5421

Even though there are some unclear points about your formulation, I'll post my solution anyways and add clarification if necessary.

Graph theoretic approach

The transformation you do to construct you 2n vertex graph is definitely sensible, since your problem becomes a shortest path problem.

If you assign the cost road fee at ri to edges (ri, r(i+1)) or road fee at li to edges (li, l(i+1)) and road switch fee si to edges (ri,l(i+1)) or (li,r(i+1)), a shortest path from x to y is also a cheapest path in your model.

Dynamic programming formulation

Because of the structure of the graph, you don't need a shortest path algorithm like Dijkstra, a simpler solution similar to the one you proposed should suffice. However when storing your array x, you have no way of determining if the optimal solution to get to a certain position i should end on road R or L.

A simple way to resolve this issue would be to store the shortest way for every paid point ri and li, i.e. store two arrays AR and AL where AR[i] is the optimal cost to get to ri (and AL[i] for li)

A simple DP formulation would be

AR[1] = AL[1] = 0 // We don't need to pay at the start
// either stay on the road or switch the road and pay changing fee:
AR[i + 1] = min(AR[i] + fee at ri, AL[i] + changing fee si)
AL[i + 1] = min(AL[i] + fee at li, AR[i] + changing fee si)

and compute the minimal cost by taking the minimum of AR[n + 1] and AL[n + 1]. To get the actual road, simply backtrack which choices were taken at every min computation.

Upvotes: 1

Related Questions