Shortest Path in a DAG Using Topological Sort

Problem Statement❯

Given a Directed Acyclic Graph (DAG) with n vertices and weighted edges, find the shortest path from a given source node to all other nodes.

For this problem, we assume that the source node is always node 0. The graph is represented using an edge list where each edge has a weight. Your task is to compute the shortest distances from the source to all other nodes using topological sorting.

Examples❯

Nodes	Edges	Output	Description
6	[[0,1,2],[0,4,1],[1,2,3],[4,2,2],[2,3,6],[4,5,4],[5,3,1]]	[0,2,3,6,1,5]	Shortest paths from node 0 using topological order and edge relaxation
3	[[0,1,5],[1,2,3]]	[0,5,8]	Path 0 → 1 → 2 accumulates weight
4	[[0,1,1],[0,2,4],[1,3,2],[2,3,1]]	[0,1,4,3]	Shortest path from 0 to 3 is via node 2
1	[]	[0]	Single node, no edges
3	[[1,2,1]]	[0, ∞, ∞]	No outgoing edges from source 0

Solution❯

To solve the shortest path problem in a DAG, we use the property that a DAG has a topological ordering. In such an ordering, for every directed edge u → v, node u appears before v.

This property allows us to process each node in the correct order and update (relax) the distances of its adjacent nodes only once. This is more efficient than Dijkstra's algorithm for DAGs.

Here's the approach:

Build an adjacency list from the edge list.
Perform a topological sort of the graph.
Initialize distances from the source to all nodes as ∞ (infinity), except the source itself which is 0.
Process each node in topological order:

For every outgoing edge from the current node, try to relax the distance to the target node.

By the end of this process, the distance array holds the shortest path distances from the source to every other node in the DAG.

Algorithm Steps❯

Construct an adjacency list from the given edges.
Perform a topological sort of the DAG using DFS.
Initialize a distance array with Infinity for all nodes, except the source (node 0) which is set to 0.
Iterate through each node in topological order:

For each neighbor v of the current node u, update dist[v] = min(dist[v], dist[u] + weight)

Return the final distance array. Nodes unreachable from source will retain Infinity.

Code

JavaScript

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]

⬅ Previous TopicShortest Path in Undirected Graph with Unit Distance

Next Topic ⮕Dijkstra's Algorithm Using Set - Shortest Path in Graph