6. Consider the following recursive algorithm for finding the shortest weighted path in an acyclic graph, from s to t(15 points) a. Why does this algorithm not work for general graphs? b. Prove that this algorithm terminates for acyclic graph c. What is the worst-case running time of the algorithm? Distance shortest(s, t)i Distance d, tmp; If(S==t) return 0 for each Vertex v adjacent to s i tmp= shortest(v, 1); if(cs, v tmp <dn) d,=Csr+ tn return d,- 4 - 6. Consider the following recursive algorithm for finding the shortest weighted path in an acyclic graph, from s to t. (15 points) a. Why does this algorithm not work for general graphs? b. Prove that this algorithm terminates for acyclic graphs. c. What is the worst-case running time of the algorithm? Distance shortest(s, t) { Distance dt, tmp; If (s = = t) return 0; dt = ∞; for each Vertex v adjacent to s { tmp = shortest(v, t); if (cs,v + tmp < dt) dt = cs,v + tmp; } return dt; }