We are given a weighted graph G = (V, E) with weights given by W. The nodes repr

Question

We are given a weighted graph G = (V, E) with weights given by W. The nodes represent cities and the edges are (positive) distances between the cities. We want to get a car that can travel between any two cities: it can leave with a full tank of gas, but cannot purchase gas until it reached its destination. The zero-stop-capacity of the car we purchase is defined to be the longest distance between any two cities that we may travel (but of course, between any two cities we would take the shortest path). A simple way to compute this is to run Floyd-Warshall (O(n^3)), and then look at all pairs of vertices/cities and return the greatest distance (O(n^2)).

A bit more formally, Floyd-Warshall returns W*, where W* [u, v] is the length of the shortest route from city u to v. The zero-stop-capacity is thus, max{ W* [u, v] | u, v E }.

Now suppose that you want to calculate the necessary one-stop-capacity of a potential car: we are allowed to stop at just one intermediate city to purchase gas for the car. Describe an algorithm to determine what capacity would be needed for our car to travel between any two cities with at most one refueling stop.

We are given a weighted graph G (VIE) with weights given by W. The nodes represent cities and the edges are (positive) distances between the cities. We want to get a car that can travel between any two cities: it can leave with a full tank of gas, but cannot purchase gas until it reached its destination. The zero stop-capacity of the car we purchase is defined to be the longest distance between any two cities that we may travel (but of course, between any two cities we would take the shortest path). A simple way to compute this is to run Floyd-Warshall (O(n')), and then look at all pairs of vertices/cities and return the greatest distance (O(n2). A bit more formally, Floyd-Warshall returns W where W Eu, vl is the length of the shortest route from city u to v. The zero-stop-capacity is thus max W lu. u, v E E Now suppose that you want to calculate the necessary one-stop-capacity of a potential car: we are allowed to stop at just one intermediate city to purchase gas for the car. Describe an algorithm to determine what capacity would be needed for our car to travel between any two cities with at most one refueling stop. [6 points]

Explanation / Answer

Let us gereralize the problem to make it simpler.

G(u,v) , U - tank capacity , - number of refilling stops allowed(later we will replace it by 1), - initial gas

edge lengths d : E -> R+, gas costs c : V -> R+

Goal : minimum cost from u to v

This is an optimization problem and looking at the sub problem structure this can be solved using greedy approach and dynamic prog approach.

Basic Idea : at each sub station find the minimum cost using remaining gas and minimum cost using this as refilling station and choose the optimum one.

Here is the Dynamic Prog approach solution :

OPTIMUM(x,q,g) = Minimum cost to go from x to t in q stops starting with g units of gas

If c(Uj) < c(Uj+1) then at Uj fill up the full tank.

If c(Uj) >= c(Uj+1) then fill enough to reach to Uj+1.

OPTIMUM = Minimum for all v { (OPTIMUM [v,q-1,0] + (d(x,v)-g) c(x) if if c(v) c(x) & d(x,v) > g ), (OPTIMUM [v,q-1,U-d(x,v)] + (U-g) c(x)) }

It will give O( n^2 logn) time complexity.

Please let me know if any query on this solution.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.