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.

Practice

1. What is the main advantage of using topological order to find the shortest path in a Directed Acyclic Graph (DAG)?

easy

A. It finds the longest path instead of the shortest.

B. It guarantees the graph has cycles.

C. It allows processing vertices in a linear order without revisiting nodes.

D. It sorts vertices based on their weights.

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges vertices so that all edges go from earlier to later vertices, ensuring no cycles.

2. Step 2: Use topological order for shortest path

   Processing vertices in this order means each vertex is processed after all its predecessors, so shortest paths can be updated without revisiting.

3. Final Answer:

   It allows processing vertices in a linear order without revisiting nodes. -> Option C

4. Quick Check:

   Topological order = linear processing without revisits [OK]

Hint: Topological order processes nodes once in DAG [OK]

Common Mistakes:

• Thinking topological order applies to graphs with cycles
• Confusing shortest path with longest path
• Assuming topological order sorts by weights

2. Which TypeScript code snippet correctly initializes the distance array for shortest path calculation in a DAG with 5 vertices?

easy

A. const dist: number[] = Array(5).fill(Infinity); dist[0] = 0;

B. const dist: number[] = new Array(5).fill(0); dist[0] = Infinity;

C. const dist: number[] = Array(5).fill(-1); dist[0] = 0;

D. const dist: number[] = new Array(5).fill(null); dist[0] = 0;

Solution

1. Step 1: Initialize distances with Infinity except source

   Distances start as Infinity to represent unknown paths; source vertex distance is 0.

2. Step 2: Check code correctness

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; uses Array(5).fill(Infinity) and sets dist[0] = 0, which is correct initialization.

3. Final Answer:

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; -> Option A

4. Quick Check:

   Distance array initialized with Infinity except source 0 [OK]

Hint: Use Infinity for unknown distances, zero for source [OK]

Common Mistakes:

• Filling distances with 0 instead of Infinity
• Setting source distance to Infinity
• Using null or -1 which are invalid for distances

3. Given the following DAG edges with weights:
edges = [[0,1,2],[0,2,4],[1,2,1],[1,3,7],[2,4,3],[3,4,1]]
and source vertex 0, what is the shortest distance array after running shortest path using topological order?

medium

A. [0, 4, 5, 8, 9]

B. [0, 2, 4, 7, 8]

C. [0, 2, 3, 7, 6]

D. [0, 2, 3, 9, 6]

Solution

1. Step 1: Calculate shortest distances step-by-step

   Start dist = [0,∞,∞,∞,∞]. From 0: dist[1]=2, dist[2]=4. From 1: dist[2]=min(4,2+1=3)=3, dist[3]=2+7=9. From 2: dist[4]=3+3=6. From 3: dist[4]=min(6,9+1=10)=6.

2. Step 2: Final shortest distances

   Distances are [0, 2, 3, 9, 6]. But check [0, 2, 3, 7, 6] has dist[3]=7, so re-check: From 1 to 3 is 7, so dist[3]=2+7=9. [0, 2, 3, 7, 6] shows 7, so [0, 2, 3, 9, 6] matches 9 for dist[3]. So [0, 2, 3, 9, 6] is correct.

3. Final Answer:

   [0, 2, 3, 9, 6] -> Option D

4. Quick Check:

   Shortest distances = [0, 2, 3, 9, 6] [OK]

Hint: Relax edges in topological order to update distances [OK]

Common Mistakes:

• Not updating distances with minimum values
• Mixing up edge weights during relaxation
• Ignoring topological order in updates

4. Identify the bug in this TypeScript code snippet for shortest path in DAG:

const dist = Array(n).fill(Infinity);
dist[0] = 0;
for (const u of topoOrder) {
  for (const [v, w] of graph[u]) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

Assuming graph is adjacency list and topoOrder is correct topological order.

medium

A. No bug; the code correctly updates shortest distances.

B. The inner loop should iterate over graph[v] instead of graph[u].

C. dist[u] should be checked for Infinity before relaxation.

D. dist array should be initialized with zeros instead of Infinity.

Solution

1. Step 1: Analyze the relaxation in topological order

   In topological order, when processing u, dist[u] has been finalized as the shortest path from source if reachable. For unreachable u, dist[u] remains Infinity.

2. Step 2: Verify Infinity handling

   In JavaScript/TypeScript, Infinity + w = Infinity for any finite w, and Infinity < dist[v] is false, so no incorrect updates occur. Thus, no explicit check is needed.

3. Final Answer:

   No bug; the code correctly updates shortest distances. -> Option A

4. Quick Check:

   Infinity + w doesn't update distances wrongly [OK]

Hint: Infinity arithmetic handles unreachable nodes [OK]

Common Mistakes:

• Thinking explicit Infinity check is required
• Iterating over wrong adjacency list
• Initializing dist with zeros

5. You have a DAG with vertices 0 to 5 and edges:
[[0,1,3],[0,2,6],[1,2,4],[1,3,4],[2,4,8],[3,4,2],[4,5,1]]
Using shortest path with topological order from source 0, what is the shortest distance to vertex 5?

hard

A. 12

B. 10

C. 11

D. 9

Solution

1. Step 1: Initialize distances and process edges

   Start dist = [0,∞,∞,∞,∞,∞]. From 0: dist[1]=3, dist[2]=6. From 1: dist[2]=min(6,3+4=7)=6, dist[3]=3+4=7. From 2: dist[4]=6+8=14. From 3: dist[4]=min(14,7+2=9)=9. From 4: dist[5]=9+1=10.

2. Step 2: Verify shortest distance to vertex 5

   Shortest distance to 5 is 10, but check if any shorter path exists: 0->1->3->4->5 = 3+4+2+1=10, 0->2->4->5=6+8+1=15. So 10 is shortest.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Shortest distance to 5 = 10 [OK]

Hint: Relax edges in topological order to find shortest path [OK]

Common Mistakes:

• Choosing longer path distances
• Ignoring better paths through intermediate vertices
• Miscomputing sums of edge weights