Shortest Path in DAG Using Topological Order in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Directed Acyclic Graph (DAG)?

A DAG is a graph with directed edges and no cycles, meaning you cannot start at one node and follow a path that loops back to the same node.

intermediate

Why do we use topological order for shortest path in a DAG?

Topological order arranges nodes so all edges go from earlier to later nodes, allowing us to relax edges in one pass without revisiting nodes, making shortest path calculation efficient.

beginner

What does 'relaxing an edge' mean in shortest path algorithms?

Relaxing an edge means checking if the current known shortest distance to a node can be improved by going through another node connected by that edge, and updating it if yes.

beginner

In the shortest path algorithm for DAG, what initial distance values do we assign to nodes?

We set the source node distance to 0 and all other nodes to infinity (or a very large number) to indicate they are not yet reachable.

intermediate

What is the time complexity of finding shortest paths in a DAG using topological order?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each node and edge is processed once.

What property must a graph have to use topological order for shortest path?

A It must be a complete graph

B It must be an undirected graph

C It must contain cycles

D It must be a Directed Acyclic Graph (DAG)

Topological order only exists for DAGs because cycles prevent a linear ordering.

What is the first step in finding shortest paths in a DAG using topological order?

A Find the topological order of the graph

B Relax all edges randomly

C Set all distances to zero

D Run Dijkstra's algorithm

We first find the topological order to process nodes in a sequence that respects edge directions.

When relaxing edges in shortest path for DAG, what do we update?

A The distance to the target node if a shorter path is found

B The number of edges in the graph

C The topological order

D The source node

Relaxing updates the shortest known distance to a node if a better path is found.

What initial distance is assigned to the source node in shortest path calculation?

A Infinity

B -1

C 0

D 1

The source node distance is set to 0 because the distance from source to itself is zero.

What is the advantage of using topological order for shortest path in DAG over Dijkstra's algorithm?

A It works with negative cycles

B It runs faster with O(V + E) time complexity

C It uses more memory

D It requires no initialization

Topological order allows processing each node once, making it faster than Dijkstra's O(E log V) in DAGs.

Explain how topological order helps in finding the shortest path in a DAG.

Think about how ordering nodes prevents revisiting.

Describe the steps to find shortest paths from a source node in a DAG using topological order.

Start from ordering, then update distances step by step.

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