Consider the recursive algorithm in Figure 10.80 for finding the shortest weighted path in an acyclic graph, from s to t.

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?

Transcribed Image Text:

Distance shortest( s,t ) Distance di, tmp; if( s == t ) return 0; de 00; for each Vertex v adjacent to s { tmp = shortest (v, t ); if( Cs,y + tmp < d¿) di = Csy + tmp; } return d;; }