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❯

Understanding the Problem

We are given a Directed Acyclic Graph (DAG) and a source node. Our goal is to find the shortest path from this source to all other nodes in the graph.

Unlike general graphs where we might use Dijkstra’s algorithm, here we can take advantage of the acyclic nature of the graph. Since there are no cycles, a topological order of nodes exists. In this order, for every directed edge u → v, node u comes before v. This means we can process each node and update distances of its neighbors in a single pass, efficiently solving the problem.

Step-by-Step Solution with Example

Step 1: Represent the Graph

Suppose we are given the following edge list for a graph with 6 nodes (0 to 5):


edges = [
  (0, 1, 2),
  (0, 4, 1),
  (1, 2, 3),
  (4, 2, 2),
  (2, 3, 6),
  (4, 5, 4),
  (5, 3, 1)
]

Each tuple (u, v, w) represents a directed edge from u to v with weight w. We first convert this into an adjacency list for easier processing.

Step 2: Topological Sort

We perform a topological sort on the DAG. This gives us an order in which we can safely process the nodes, ensuring that all prerequisites for a node are processed before it.

For the above graph, one possible topological order is: [0, 1, 4, 5, 2, 3].

Step 3: Initialize Distances

We set up an array dist to keep track of the shortest distance from the source node to every other node. Initially, all distances are set to infinity except for the source (let's say source is node 0), which is set to 0:


dist = [0, ∞, ∞, ∞, ∞, ∞]

Step 4: Process Nodes in Topological Order

Now we traverse the nodes in topological order. For each node, we look at its outgoing edges and try to "relax" them. Relaxing means: if the current known distance to the neighbor is greater than the distance to the current node plus the edge weight, we update it.

Let's walk through it:

From node 0 → 1 (weight 2): dist[1] = min(∞, 0+2) = 2
From node 0 → 4 (weight 1): dist[4] = min(∞, 0+1) = 1
From node 1 → 2 (weight 3): dist[2] = min(∞, 2+3) = 5
From node 4 → 2 (weight 2): dist[2] = min(5, 1+2) = 3
From node 4 → 5 (weight 4): dist[5] = min(∞, 1+4) = 5
From node 5 → 3 (weight 1): dist[3] = min(∞, 5+1) = 6
From node 2 → 3 (weight 6): dist[3] = min(6, 3+6) = 6 (no change)

Final dist array: [0, 2, 3, 6, 1, 5]

Edge Cases

Disconnected Nodes: If a node is not reachable from the source, its distance will remain ∞. Always check for such cases before interpreting the results.
Multiple Valid Topological Orders: The topological sort is not unique. As long as it's a valid topological order, the final distances will be the same.
Zero-weight Edges: Edges with weight 0 are still valid and can affect shortest paths. Our relaxation logic should include them.
Negative Weights: Since we’re in a DAG, negative edge weights are safe and won’t create cycles. The algorithm works fine with them.

Finally

Using topological sort for shortest path in DAGs is optimal and elegant. It avoids unnecessary overhead of priority queues or repeated visits. Understanding how topological order guarantees that each node is processed only after all of its dependencies is the key to this approach.

Just remember: this method only works for DAGs. If your graph has cycles, you must use other algorithms like Dijkstra or Bellman-Ford depending on the context.

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

Comments

Loading comments...