Problem 2: All-Pairs Shortest Paths with Mandatory Vertices (40 Points) Consider a graph G = (V, E) where some vertices are colored blue. Let B CV be the set of blue vertrices. Our goal is to compute all pairs shortest paths such that each shoretest path uses at least one blue vertex (if either i orj is blue then this immediately satisfies the constraint without posing any restrictions on the path). a. (5 Points) Compute all-pairs shortest paths under this constraint where there is exactly one blue vertex, i.e., Bl = 1. The running time of your algorithm should be O(n). b. (15 Points) Compute all-pairs shortest paths under this constraint for an arbitrary number of blue vertices B 1. The running time of your algorithm should be O(n). c. (20 Points) Consider the stricter constraint that each shortest path uses at least at least two blue vertices. Compute all-pairs shortest paths under this new constraint for an arbitrary number of blue vertices Bl> 2. The running time of your algorithm should be O(n). (Hint: Consider the sub-problem structure d(i,j): the shortest path between vertices vi and v; that uses intermediate vertices 01, ..., Uk where at least I blue blue vertices for 1 = 0,1,2. What is d (1,1)?) 5 01 V4 N 4 5 10 1 2 U3 05 Figure 1: Without any restriction the shortest path between U, and v4 is 02 +13 +04 for a cost of 6. If the path needs to have one blue vertex then the optimal path remains 03 V4 since uz is a blue vertex. If the path needs to have two blue vertices then the optimal path is 02 +23+01 + 4 for a cost of 10