Explain and fully answer each step with detail.

3. (25 pts) One can use graph traversal techniques to find shortest path from a vertex u to a vertex v in an unweighted graph G = (V, E). (a) (5 pts) One possible technique is to perform a depth first search starting at u and count the number of steps it takes to find the vertex v. Give a counterexample to show that this does not compute the shortest path (b) (10 pts) Another way is to use breadth first search starting at u and count the number of steps it takes to reach the vertex v. Sketch the details of this technique and show that this indeed computes the shortest path from u to r in G (c) (10 pts) Now the edges of G are assigned weights from the set (1, 2,3,4). That is, for every edge e E E, wt(e) e 11, 2,3, 4). Can you compute the shortest path from u to u in 0(IVI+1 ) time? Hint: Modify G in some way and run algorithm from (b)