Shortest Path in DAG Using Topological Order in DSA Javascript

Mental Model

We find the shortest path in a graph with no cycles by first ordering nodes so all edges go forward, then relaxing edges in that order.

Analogy: Imagine tasks that depend on others; you do them in order so you never do a task before its dependencies. This order helps find the quickest way to finish all tasks.

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

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

Dry Run Walkthrough

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

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

Step 1: Find topological order of nodes

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

Why: We need an order where all edges go forward to relax edges correctly

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

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

Why: Start node distance is zero; others unknown yet

Step 3: Relax edges from node 0: update dist[1]=2, dist[2]=4

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

Why: Edges from 0 give initial shortest paths to 1 and 2

Step 4: Relax edges from node 1: update dist[2]=3 (2+1), dist[3]=9 (2+7)

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

Why: Better path to 2 found via 1; set dist to 3; dist to 3 updated

Step 5: Relax edges from node 2: update dist[4]=6 (3+3)

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

Why: Found path to 4 via 2

Step 6: Relax edges from node 4: update dist[3]=7 (6+1)

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

Why: Better path to 3 found via 4

Step 7: Node 3 has no outgoing edges; done

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

Why: All nodes processed; shortest distances found

Result:

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

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.adj = new Array(vertices).fill(0).map(() => []);
  }

  addEdge(u, v, w) {
    this.adj[u].push({ node: v, weight: w });
  }

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

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

    // Step 1: Get topological order
    for (let i = 0; i < this.V; i++) {
      if (!visited[i]) {
        this.topologicalSortUtil(i, visited, stack);
      }
    }

    const dist = new Array(this.V).fill(Infinity);
    dist[start] = 0; // distance to start is zero

    // Step 2: Process nodes in topological order
    while (stack.length > 0) {
      const u = stack.pop(); // get next node in order

      if (dist[u] !== Infinity) {
        for (const neighbor of this.adj[u]) {
          if (dist[neighbor.node] > dist[u] + neighbor.weight) {
            dist[neighbor.node] = dist[u] + neighbor.weight; // relax edge
          }
        }
      }
    }

    // Print distances
    for (let i = 0; i < this.V; i++) {
      if (dist[i] === Infinity) {
        console.log(`Distance from ${start} to ${i}: Infinity`);
      } else {
        console.log(`Distance from ${start} to ${i}: ${dist[i]}`);
      }
    }
  }
}

// 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(4, 3, 1);

g.shortestPath(0);

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

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

dist[start] = 0; // distance to start is zero

Initialize start node distance to zero

const u = stack.pop(); // get next node in order

Process nodes in topological order by popping from stack

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

Only relax edges from nodes reachable from start

if (dist[neighbor.node] > dist[u] + neighbor.weight) {

Relax edge if shorter path found

dist[neighbor.node] = dist[u] + neighbor.weight; // relax edge

Update distance to neighbor with shorter path

Output

Distance from 0 to 0: 0

Distance from 0 to 1: 2

Distance from 0 to 2: 3

Distance from 0 to 3: 7

Distance from 0 to 4: 6

Complexity Analysis

Time: O(V + E) because we do a topological sort (O(V+E)) and then relax each edge 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 topological order

Edge Cases

Graph with no edges

Distances remain Infinity except start node which is zero

DSA Javascript

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

Start node isolated (no outgoing edges)

Only start node distance is zero; others remain Infinity

DSA Javascript

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

Graph with multiple disconnected components

Distances to unreachable nodes remain Infinity

DSA Javascript

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 performing topological sort before relaxing edges
Fix: Always get topological order first to ensure edges are relaxed in correct sequence

Mistake: Relaxing edges from nodes with infinite distance
Fix: Check if current node distance is not Infinity before relaxing edges

Summary

Finds shortest paths in a directed acyclic graph by relaxing edges in topological order.

Use when the graph has no cycles and you want an efficient shortest path solution.

The key is to process nodes so all edges go forward, ensuring each edge is relaxed once.

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 allows processing nodes in a linear order without revisiting them.

B. It guarantees the graph has cycles.

C. It sorts nodes based on their weights.

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

Solution

1. Step 1: Understand topological order in DAG

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

2. Step 2: Use topological order for shortest path

   Processing nodes in this order means each node is visited once, and distances can be updated efficiently without revisiting.

3. Final Answer:

   It allows processing nodes in a linear order without revisiting them. -> Option A

4. Quick Check:

   Topological order = linear processing without revisits [OK]

Hint: Topological order processes nodes once for shortest path [OK]

Common Mistakes:

• Thinking topological order sorts by weights
• Assuming DAG has cycles
• Confusing shortest path with longest path

2. Which of the following JavaScript code snippets correctly initializes the distance array for shortest path calculation in a DAG with 5 nodes, starting from node 0?

easy

A. const dist = Array(5).fill(-1); dist[0] = 0;

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

C. const dist = Array(5).fill(null); dist[0] = 0;

D. const dist = Array(5).fill(Infinity); dist[0] = 0;

Solution

1. Step 1: Initialize distances for shortest path

   Distances to all nodes except start should be Infinity to represent unknown paths.

2. Step 2: Set start node distance to zero

   Distance to start node (0) is zero because it is the source.

3. Final Answer:

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

4. Quick Check:

   Start distance 0, others Infinity [OK]

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

Common Mistakes:

• Setting start node distance to Infinity
• Using 0 for all distances initially
• Using null or -1 which are invalid for distances

3. Consider the following DAG represented as adjacency list with weights:

const graph = {
  0: [[1, 2], [2, 4]],
  1: [[2, 1], [3, 7]],
  2: [[4, 3]],
  3: [[4, 1]],
  4: []
};

If we run shortest path from node 0 using topological order, what is the shortest distance to node 4?

medium

A. 6

B. 7

C. 10

D. 9

Solution

1. Step 1: Find topological order and initialize distances

   Topological order could be [0,1,2,3,4]. Initialize dist = [0, Infinity, Infinity, Infinity, Infinity].

2. Step 2: Relax edges in topological order

   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.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest distance to node 4 = 6 [OK]

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

Common Mistakes:

• Not updating dist[2] to smaller value 3
• Ignoring edge from 3 to 4
• Adding weights incorrectly

4. The following code attempts to find the shortest path in a DAG using topological order but has a bug:

function shortestPath(graph, start) {
  const dist = Array(Object.keys(graph).length).fill(Infinity);
  dist[start] = 0;
  const topoOrder = topologicalSort(graph);
  for (const node of topoOrder) {
    for (const [neighbor, weight] of graph[node]) {
      if (dist[node] + weight < dist[neighbor]) {
        dist[neighbor] = dist[node] + weight;
      }
    }
  }
  return dist;
}

What is the likely cause of incorrect results?

medium

A. The start node distance is not set to zero

B. dist array is initialized with zeros instead of Infinity

C. topologicalSort function might return nodes in wrong order

D. The graph edges are not weighted

Solution

1. Step 1: Check initialization and start distance

   dist is correctly initialized with Infinity and start node distance set to 0.

2. Step 2: Verify topological order correctness

   If topologicalSort returns nodes in wrong order, relaxation will fail and distances won't update correctly.

3. Final Answer:

   topologicalSort function might return nodes in wrong order -> Option C

4. Quick Check:

   Correct topological order needed for shortest path [OK]

Hint: Ensure topological order is correct before relaxing edges [OK]

Common Mistakes:

• Assuming dist initialization is wrong
• Ignoring importance of topological order
• Forgetting to set start node distance

5. Given a DAG with nodes 0 to 5 and edges with weights:

0 -> 1 (3), 0 -> 2 (2), 1 -> 3 (4), 2 -> 3 (1), 3 -> 4 (2), 4 -> 5 (1)

If you want to find the shortest path from node 0 to node 5 using topological order, which sequence of distances will you get before processing node 3?

hard

A. [0, 3, 2, 5, Infinity, Infinity]

B. [0, 3, 2, 3, Infinity, Infinity]

C. [0, 3, 2, 3, 2, Infinity]

D. [0, 3, 2, 1, Infinity, Infinity]

Solution

1. Step 1: Initialize distances and process nodes 0,1,2

   Start dist = [0, Infinity, Infinity, Infinity, Infinity, Infinity]. After 0: dist[1]=3, dist[2]=2. After 1: dist[3]=3+4=7. After 2: dist[3]=min(7,2+1=3)=3.

2. Step 2: Before processing node 3

   At this point, node 3's distance has been finalized by its predecessors to 3, but outgoing edges from 3 have not been relaxed yet, so dist[4] and dist[5] remain Infinity. Distances: [0, 3, 2, 3, Infinity, Infinity].

3. Final Answer:

   [0, 3, 2, 3, Infinity, Infinity] -> Option B

4. Quick Check:

   Distances before relaxing node 3 edges [OK]

Hint: Check distances before relaxing edges from current node [OK]

Common Mistakes:

• Updating distances of neighbors too early
• Confusing order of relaxation
• Miscomputing minimum distances