You are the chief trade minister under Emperor Caesar Augustus with the job of directingtrade in the ancient world. The Emperor has proclaimed thatall roads lead to (and from)Rome; that is, all trade must go through Rome. In particular, you are given a stronglyconnected directed graph G= (V, E) with positive edge weights, and there is a particularnodev0∈V(Rome). Give an efficient algorithm for finding shortest path betweenall pairsof nodes, with the one restriction that these paths must all pass through v0 (Rome). Make your algorithm as efficient as you can, perhaps as fast as Dijkstra’s algorithm. Required:
a. Give the efficient algorithm.
b. Occasionally, Augustus will ask you for the (smallest) distance between two vertices. Youwant to do this as quickly as possible, so that Augustus does not have your head. This is called adistance query: Given a pair of vertices (u, v), give the the distance ofthe shortest path that passes throughv0. Describe how you might store the results suchthat you require O(|V|) storage and from your data structure you can compute the result in O(1) time. For your answer, a clear description of the data structure and its usage issufficient.
c. On the other hand, the traders need to know the paths themselves. This is called apath query: Given a part of vertices (u, v), give the shortest path itself, that passes throughv0. Describe how you might store the results such that you requireO(|V|) storage and from your data structure you can compute the result in O(|V|) time. Again, a clear description of the data structure and its usage is sufficient.