Topological sort; job completion times & longest path in a DAG

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}