Question 2 (SPTree Verification) You are given a directed weighted graph G = (V, E,W), a verter s e V and a tree T such that each verter vi EV maps to a node in T. The root of T is s. For each node n in T we define the predecessor n. as its parent in the tree. By definition, s.r =Nil for the root node s. For any other node ni. = 12, there must be a direct edge (n2, n) E E. You need to develop an algorithm that tests whether T is a shortest-path tree 1 from the single-sources to all destinations in G. In particular, the algorithm should return true if T is a shortest path tree and false, otherwise. Notice that your algorithm should be more efficient than the Bellman-Ford algorithm which runs in O( VE). An example is given in the figure below. Assume that for the graph G we would like to test two trees rooted at A. The first tree, Ti is a shortest path tree. Your algorithm should return true when running on G.T. On the other hand, the tree Tis not a shortest path tree and your algorithm should return false. 18 18 ) 12 12 3 (a) Graph G (b) Tree Ti (c) Tree T2