Shortest Path in DAG Problem

Shortest Path in DAG Problem — ExecCode Hard DSA Practice

Solve the Shortest Path in DAG problem on ExecCode. Free online hard DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Given a weighted DAG with n nodes and directed edges [u,v,w], compute shortest-path distances from source src to every node by topologically sorting then relaxing edges in that order. Return the dist array (use Infinity for unreachable if needed).

Examples

Input n = 7, edges = [[0, 1, 2], [0, 4, 1], [1, 2, 3], [4, 2, 2], [4, 5, 4], [2, 3, 6], [5, 3, 1], [2, 6, 1], [6, 3, 1]], src = 0; Output [0, 2, 3, 5, 1, 5, 4]. Input n = 3, edges = [[0, 1, 1]], src = 0; Output [0, 1, null]

Constraints

1 ≤ n ≤ 10^5 0 ≤ edges.length ≤ 2*10^5 Weights may be negative (but no cycles) 0 ≤ src < n

Practice Shortest Path in DAG free on ExecCode. Browse DSA problems, topic map, and placement guides.