Constructing and extracting the solution for Longest Path

Below is an algorithm to compute the longest weighted simple path from s to t.

Longest-Path-Value-Memoized (G, u, t, dist)

if u = t

dist[u] = 0 // caller may expect all entries defined

return 0

if dist[u] > -

return dist[u] // this is the reuse of prior result

else

// dist[u] = - is not necessary as caller did it

for each v in G.Adj[u]

alt = w(u,v)

+ Longest-Path-Value-Memoized(G, v, t, dist)

if dist[u] < alt

dist[u] = alt

return dist[u]

(a) Rewrite LongestPathValueMemoized to LongestPathMemoized that takes an additional parameter next[1..|V|], and records the next vertex in the path from any given vertex u in next[u]. Assume that all entries of next are initialized to 1 by the caller.

(b) Once that is done, write a procedure that recovers (e.g., prints) the path from s to t by tracing through next.

(c) What is the asymptotic runtime of your total solution to the Longest Path problem in terms of |V| and |E|? Include all steps (initializing arrays, LongestPathMemoized, and printing the solution). Hint: Count in aggregate across all calls rather than trying to figure out how many times the loop runs on a given Adj[u].

(d) What is the asymptotic use of space of your solution in terms of |V| and |E|?