Shortest Path in DAG Using Topological Order in DSA Typescript - Time & Space Complexity

Time Complexity: Shortest Path in DAG Using Topological Order

O(n + e)

Understanding Time Complexity

We want to understand how long it takes to find the shortest path in a Directed Acyclic Graph (DAG) using topological order.

Specifically, how the time grows as the graph gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function shortestPathDAG(graph: Map<number, Array<[number, number]>>, start: number, n: number): number[] {
  const dist = Array(n).fill(Infinity);
  dist[start] = 0;
  const topoOrder = topologicalSort(graph, n);

  for (const u of topoOrder) {
    if (dist[u] !== Infinity) {
      for (const [v, weight] of graph.get(u) || []) {
        if (dist[u] + weight < dist[v]) {
          dist[v] = dist[u] + weight;
        }
      }
    }
  }
  return dist;
}
    

This code finds shortest distances from a start node to all others in a DAG using topological order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop goes through each node once in topological order.
• Nested operation: For each node, it loops through all its edges (neighbors).
• How many times: Each edge is checked exactly once during the nested loop.

How Execution Grows With Input

As the number of nodes (n) and edges (e) grow, the code visits each node once and each edge once.

Input Size (n, e)	Approx. Operations
10 nodes, 15 edges	About 25 operations (10 for nodes + 15 for edges)
100 nodes, 200 edges	About 300 operations (100 + 200)
1000 nodes, 5000 edges	About 6000 operations (1000 + 5000)

Pattern observation: Operations grow roughly in a straight line with the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time to find shortest paths grows linearly with the number of nodes plus edges in the graph.

Common Mistake

[X] Wrong: "The algorithm checks all possible paths, so it must be exponential time."

[OK] Correct: Because the graph is a DAG and we use topological order, each edge and node is processed only once, avoiding repeated work.

Interview Connect

Understanding this time complexity helps you explain why topological order is efficient for shortest paths in DAGs, a common interview topic.

Self-Check

What if the graph had cycles? How would the time complexity and approach change?

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