Shortest Path in a DAG
Using Topological Sort

function shortestPathDAG(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) {
    adj[u].push([v, w]);
  }

  const visited = new Array(n).fill(false);
  const stack = [];

  function topoSort(node) {
    visited[node] = true;
    for (const [neighbor] of adj[node]) {
      if (!visited[neighbor]) {
        topoSort(neighbor);
      }
    }
    stack.push(node);
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) topoSort(i);
  }

  const dist = new Array(n).fill(Infinity);
  dist[0] = 0;

  while (stack.length) {
    const node = stack.pop();
    if (dist[node] !== Infinity) {
      for (const [neighbor, weight] of adj[node]) {
        if (dist[node] + weight < dist[neighbor]) {
          dist[neighbor] = dist[node] + weight;
        }
      }
    }
  }

  return dist;
}

// Example usage:
console.log("Shortest Path:", shortestPathDAG(6, [[0,1,2],[0,4,1],[1,2,3],[4,2,2],[2,3,6],[4,5,4],[5,3,1]])); // Output: [0,2,3,6,1,5]