Bottom up longest path algorithm Consider the following recu

Bottom up longest path algorithm!

Consider the following recursive (top-down) dynamic programming solution to the longest paths problem that records the vertices on the longest path by using an additional parameter next[1.. |v|] that records the next vertex in the path from any given vertex u in next [u]. (We assuming that all entries of next are initialized to nil by the caller) Longest-Path-Memoized (G, u, t, dist, next) if u = t dist[u] = 0 return 0 if dist[u] > -infinity return dist[u] else for each v in G.Adj[u] alt = w (u, v) + Longest-Path-Memoized(G, v, t, dist, next) if dist[u]

Solution

Longest-path-bottom-up(G,t,u,dist,parent)

   if u==t

     dist[u]=0;

return 0;

if dist[t] > -infinity

return dist[t];

else

   for each vertex v in G.Adj(t)

   alt=w(v,t)+Longest- path-bottom-up(G,v,u,dist,parent);

      if dist[t] < alt.

            dist[t]=alt;

            parent[t]=v;

return dist[t];

b) This algorithm is almost same as the given longest top bottom algorithm but here instead of next we consider the parent term and source in bottom up approach will be the destination in the top bottom approach hence the process will start from the lower node and then moving towards the destination by considering the parent of the current node

In the given algorithm, first check whether source and destination are equal then return 0 if not consider all the adjacent nodes of current node and consider a node and call the recursive function and finally if it reaches destination a value wiill be computed and this process is repeated for all the adjacent nodes and compared with the other paths and based on the comparsion the result will be considered..

Topological sort is useful this is because recursive functions provides a virtualization and solves the given problem and hence considering only the adjacent of current node makes a sense of small problem and including this small problem for all the nodes in the given graph means a larger problem and can be easily solved...

c)

   It is almost works like the top-bottom approach which consider the source as destination and destination as its source the asymptotic run time for the Longest-Path-Bottom-Up approach have O(V+E)

where V=number of vertices.

           E=number of edges