Shortest Path in DAG Using Topological Order in DSA Typescript

Mental Model

We find the shortest path in a graph with no cycles by visiting nodes in order so that all edges go forward, updating shortest distances as we go.

Analogy: Imagine a line of dominoes set up so each domino can only knock down the next ones ahead, never behind. We knock them down in order, making sure each domino's fall time is the shortest possible.

Graph (DAG):
0 -> 1 -> 3
 ↓    ↓
  2 -> 4

Topological order: 0 -> 1 -> 2 -> 3 -> 4

Dry Run Walkthrough

Input: Graph edges with weights: 0->1(2), 0->2(4), 1->2(1), 1->3(7), 2->4(3), 3->4(1); start node: 0

Goal: Find shortest distances from node 0 to all others using topological order

Step 1: Find topological order: 0 -> 1 -> 2 -> 3 -> 4

Topological order: [0, 1, 2, 3, 4]

Why: We need to process nodes so all edges go forward, ensuring correct distance updates

Step 2: Initialize distances: dist[0]=0, others=∞

Distances: [0, ∞, ∞, ∞, ∞]

Why: Start node distance is zero; others unknown yet

Step 3: Process node 0: update dist[1]=min(∞,0+2)=2, dist[2]=min(∞,0+4)=4

Distances: [0, 2, 4, ∞, ∞]

Why: From 0, we can reach 1 and 2 with weights 2 and 4

Step 4: Process node 1: update dist[2]=min(4,2+1)=3, dist[3]=min(∞,2+7)=9

Distances: [0, 2, 3, 9, ∞]

Why: From 1, we can improve distance to 2 and set distance to 3

Step 5: Process node 2: update dist[4]=min(∞,3+3)=6

Distances: [0, 2, 3, 9, 6]

Why: From 2, we can reach 4 with weight 3

Step 6: Process node 3: update dist[4]=min(6,9+1)=6 (no change)

Distances: [0, 2, 3, 9, 6]

Why: From 3, distance to 4 is 10 which is not better than 6

Step 7: Process node 4: no outgoing edges, distances unchanged

Distances: [0, 2, 3, 9, 6]

Why: No further updates possible

Result:

Final shortest distances: 0 -> 0, 1 -> 2, 2 -> 3, 3 -> 9, 4 -> 6

Annotated Code

DSA Typescript

class Graph {
  vertices: number;
  adjList: Map<number, Array<[number, number]>>;

  constructor(vertices: number) {
    this.vertices = vertices;
    this.adjList = new Map();
    for (let i = 0; i < vertices; i++) {
      this.adjList.set(i, []);
    }
  }

  addEdge(u: number, v: number, w: number) {
    this.adjList.get(u)?.push([v, w]);
  }

  topologicalSortUtil(v: number, visited: boolean[], stack: number[]) {
    visited[v] = true;
    for (const [neighbor] of this.adjList.get(v)!) {
      if (!visited[neighbor]) {
        this.topologicalSortUtil(neighbor, visited, stack);
      }
    }
    stack.push(v); // add node after visiting neighbors
  }

  shortestPath(start: number): number[] {
    const visited = new Array(this.vertices).fill(false);
    const stack: number[] = [];

    // Step 1: Topological sort
    for (let i = 0; i < this.vertices; i++) {
      if (!visited[i]) {
        this.topologicalSortUtil(i, visited, stack);
      }
    }

    stack.reverse(); // reverse to get correct order

    // Step 2: Initialize distances
    const dist = new Array(this.vertices).fill(Infinity);
    dist[start] = 0;

    // Step 3: Relax edges in topological order
    for (const u of stack) {
      if (dist[u] !== Infinity) {
        for (const [v, w] of this.adjList.get(u)!) {
          if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w; // update shorter distance
          }
        }
      }
    }

    return dist;
  }
}

// Driver code
const g = new Graph(5);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 4);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 7);
g.addEdge(2, 4, 3);
g.addEdge(3, 4, 1);

const startNode = 0;
const distances = g.shortestPath(startNode);

for (let i = 0; i < distances.length; i++) {
  console.log(`Distance from ${startNode} to ${i} is ${distances[i]}`);
}

stack.push(v); // add node after visiting neighbors

Add node to stack after all its descendants are visited to get topological order

stack.reverse(); // reverse to get correct order

Reverse stack to get nodes in topological order

dist[start] = 0;

Set start node distance to zero

if (dist[u] !== Infinity) {

Only process nodes reachable from start

if (dist[v] > dist[u] + w) {

Relax edge if shorter path found

dist[v] = dist[u] + w; // update shorter distance

Update distance to neighbor

Output

Distance from 0 to 0 is 0

Distance from 0 to 1 is 2

Distance from 0 to 2 is 3

Distance from 0 to 3 is 9

Distance from 0 to 4 is 6

Complexity Analysis

Time: O(V + E) because we do a topological sort (O(V + E)) and then relax edges once (O(E))

Space: O(V + E) for adjacency list and auxiliary arrays like visited and distance

vs Alternative: Compared to Dijkstra's algorithm, this is faster for DAGs because no priority queue is needed and edges are relaxed once in order

Edge Cases

Graph with no edges

Distances remain infinity except start node which is zero

DSA Typescript

dist[start] = 0;

Start node with no outgoing edges

Only start node distance is zero, others remain infinity

DSA Typescript

if (dist[u] !== Infinity) {

Disconnected nodes

Distances to unreachable nodes remain infinity

DSA Typescript

if (dist[u] !== Infinity) {

When to Use This Pattern

When you see a graph with no cycles and need shortest paths, use topological order to relax edges efficiently without complex data structures.

Common Mistakes

Mistake: Not reversing the stack after DFS to get correct topological order
Fix: Reverse the stack before processing nodes for shortest path

Mistake: Relaxing edges without checking if current node distance is infinity
Fix: Only relax edges from nodes with known distances

Summary

Finds shortest paths in a graph with no cycles by processing nodes in topological order.

Use when the graph is a Directed Acyclic Graph and you want efficient shortest path calculation.

The key insight is that topological order ensures all edges go forward, so distances can be updated in one pass.