1. Shortest paths are not always unique: sometimes there are two or more different paths between two vertices, with the minimum possible length. Now consider the following problem. Input: A directed, edge-weighted graph G = (V,E), a source vertex s € V Output: A boolean array usp [-] such that for each vertex u € V, the entry usp[u] is True if and only if there is a unique shortest path from s to u. Note: usp[s] =True. (a) For the following directed, edge-weighted graph and given source vertex s, write down the values in the array usp[-]. 5 2 1 3 3 b 4 Sat all entries to The in usp ET TT TT] "s'a'b'c'd Check all possible paths to each vertex to a 2 poride paths A: stasba Both Tay in S 50 a is not anique C: SAC 6; 576C 7 Unre d: 5>>d=8; 576+0=4 Unique [T, F, T Sa (b) Given a directed graph with n vertices and m edges, describe an algorithm that solves the above problem in O((m + n) log n) time. Hint: Your starting point should be Dijkstra's shortest path algorithm. Note: Use the top of the next page for your answer.