Consider a directed graph G whose edges e have lengths we wi

Consider a directed graph G whose edges e have lengths w(e), with the additional property that the graph has no directed cycles.

(a) Give an efficient algorithm that, for some vertices s, t, finds a longest path from s to t. [Hint: use dynamic programming.]

(b) Give an efficient algorithm that computes the number of paths from s to t.

Solution

1)

Initialize dist[] = {NINF, NINF, ….} and dist[s] = 0 where s is the source vertex. Here NINF means negative infinite.
Create a toplogical order of all vertices.
Do following for every vertex u in topological order.
Do following for every adjacent vertex v of u
if (dist[v] < dist[u] + weight(u, v)) ………………………dist[v] = dist[u] + weight(u, v)

2)