 All Problems
Longest Path in Directed Acyclic Graph
medium
topological sort
graph
dynamic programming
amazon
google
microsoft

Given a Directed Acyclic Graph with V vertices (0 to V-1) and weighted edges, find the longest path from any source vertex (in-degree 0). Return the length of the longest path.

Example:

Input: V=6, edges=[[0,1,5],[0,2,3],[1,3,6],[1,4,8],[2,4,7],[3,5,4],[4,5,2]]
Output: 19  (path 0→1→4→5 = 5+8+2=15; or 0→1→3→5=5+6+4=15; check 0→1→4→5=15)

Constraints:

  • 1 <= V <= 10^4
  • All edge weights >= 0
Run to check your code against the sample cases, or submit to run every case