Topological sort; job completion times & longest path in a DAG
Problem
Using a topological order: (1) print a valid ordering; (2) each job takes 1 unit of time and can start only after its prerequisites finish — find the earliest completion time of every job; (3) find the longest weighted path from a source in a DAG.
Example 1
Input: jobs: n = 4, edges 1→2, 1→3, 2→4, 3→4 Output: completion times: 1, 2, 2, 3
Also asked as: Implement Topological Sort · Minimum time taken by each job to be completed given by a Directed Acyclic Graph · Longest path in a Directed Acyclic Graph
Test cases
Case 1
Input: 4, [[0,1,3],[0,2,2],[1,3,4],[2,3,1]] Expected: 7
Case 2
Input: 4, [[0,1,1],[1,2,1],[2,3,1],[0,3,2]] Expected: 3
Case 3
Input: 2, [[0,1,5]] Expected: 5
Case 4
Input: 3, [] Expected: 0
View solutionHide solution1 approach
1. Kahn's order, then relax in that order
Time O(V + E)Space O(V + E)
Process nodes in topological order. Job time: finish[v] = 1 + max(finish[u]) over predecessors. Longest path: dist[v] = max(dist[u] + w) — a simple DP once the order is fixed.
function longestPathDAG(n, edges) { // edges: [u, v, w] const adj = Array.from({ length: n }, () => []); const indeg = new Array(n).fill(0); for (const [u, v, w] of edges) { adj[u].push([v, w]); indeg[v]++; } const q = []; for (let i = 0; i < n; i++) if (!indeg[i]) q.push(i); const dist = new Array(n).fill(0); for (let i = 0; i < q.length; i++) { const u = q[i]; for (const [v, w] of adj[u]) { dist[v] = Math.max(dist[v], dist[u] + w); if (--indeg[v] === 0) q.push(v); } } return Math.max(...dist);}