Given an acyclic, directed graph G=(V,E) with positive edge weights. You are asked to find in polynomial time a longest path from a given source to every other node.

a. Use a depth-first traversal to find a path from the source one at a time and mark the longest path so far. The one that is marked when the algorithm stops is the longest path.

b. Change each edge's weight w(u,v) to w'(u,v) = -w(u,v) and then find the shortest paths from the source using the Bellman-Ford algorithm.

c. Change each edge's weight w(u,v) to w'(u,v) = -w(u,v) and then find the shortest paths using Dijkstra's algorithm.

d. Compute all paths from the source using a breadth-first traversal and select the one that is the longest.