5. (20 points) You have been hired by Uber to improve their service by finding d

Question

5. (20 points) You have been hired by Uber to improve their service by finding drivers who can get to a customer faster for pick up. Consider a graph that represents city streats, where a given path from some vertex V to W can be reversed to go from W to V and take the same amount of time in either direction. Assume that weights are given in some unit of distance (e.g., kilometers) and that the speed (km/hr) is the same on all roads. Weights are not shown in the graph below, but each weight could be any positive integer. (a) (5 points) Vertex T is at leastdistance units away from Vertex S. (b) (10 points) Consider a customer at vertex S in the graph above. Assume that each vertex has at most one driver located at that vertex. A vertex does not necessarily host any driver. How would you use Dijstra's shortest-path algorithm to find k drivers who could arrive at vertex S at a time no later than any of the other drivers

Explanation / Answer

Solution:

a)

The minimum distance can be 3 unit of distance.

b)

The Dijkstra's will be applied here in such a way that the customer will be considered as the source vertex,

and since Dijkstra's is all pair shortest path algorithm we,

will be calculating the shortest path from customer vertex to all other vertices where the drivers are present.

the vertices which have the same value k for the distance from the customer vertex will be returned as the rersult from the algorithm.

c)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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