Dijkstra's algorithm for finding a shortest-path tree and Prim's algorithm for finding a minimum spanning tree both effectively build the tree by adding low-weight edges, but they have different goals and need not produce exactly the same output (a) Give an example of a weighted, undirected graph G with a designated vertex s such that Dijkstra's algorithm on G starting from s and Prim's algorithm on G starting from s produce different results. (Try to make your example as simple as possible.) (b) Suppose that after running Prim's algorithm on G with starting vertex s and producing a minimum spanning tree T, you would like to check whether T' is also the shortest path tree in G starting from s. You could do this using Dijkstra'a algorithm, but that would take time O(m + n) log n). Show (by giving an explicit algorithm) that in fact it is possible to determine whether T is the shortest path tree in only O(m+n) time. Your algorithm can take as input G (including its edge weights), s, and T, where T is represented by specifying the parent of each vertex. Prove both that your algorithm is correct and that its running time is O(mn). You can assume that all edge weights and shortest path lengths are distinct