Shortest Path in DAG Using Topological Order in DSA C++ - 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 vertex and follow a path that loops back to it.

intermediate

Why do we use topological order to find the shortest path in a DAG?

Topological order arranges vertices so all edges go from earlier to later vertices, allowing us to relax edges in one pass without revisiting nodes.

beginner

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

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

beginner

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

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

intermediate

What is the time complexity of finding the shortest path 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 vertex and edge is processed once.

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

A It must be a Directed Acyclic Graph (DAG)

B It must be undirected

C It must have cycles

D It must be a tree

Only DAGs have a valid topological order because they have no cycles.

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

A Find the topological order of vertices

B Relax all edges randomly

C Initialize all distances to zero

D Run Dijkstra's algorithm

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

When relaxing edges in topological order, how many times is each edge processed?

A Never

B Twice

C Multiple times until no changes

D Once

Each edge is relaxed exactly once in topological order, making the algorithm efficient.

What value do we assign to the source vertex distance before starting relaxation?

A -1

B Infinity

C 0

D Random number

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

Why can't we use topological order shortest path algorithm on graphs with cycles?

A Because cycles make distances negative

B Because topological order does not exist for graphs with cycles

C Because cycles increase the number of vertices

D Because cycles make the graph undirected

Graphs with cycles do not have a topological order, so this method cannot be applied.

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

Think about how ordering vertices prevents revisiting.

Describe the steps to find the shortest path from a source vertex in a DAG using topological order.

Start from initialization and end with final distances.

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

B. It guarantees the graph has no cycles.

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

D. It works only for undirected graphs.

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges vertices so that all edges go from earlier to later vertices, allowing linear processing.

2. Step 2: Use topological order for shortest path

   Processing vertices in this order ensures each vertex is relaxed once, avoiding revisits and cycles.

3. Final Answer:

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

4. Quick Check:

   Topological order = linear processing without revisits [OK]

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

Common Mistakes:

• Thinking it works for graphs with cycles
• Confusing shortest path with longest path
• Assuming it works for undirected graphs

2. Which of the following C++ code snippets correctly initializes the distance array for shortest path calculation in a DAG with n vertices, assuming source vertex is 0?

easy

A. std::vector<int> dist(n, 0); dist[0] = INT_MAX;

B. std::vector<int> dist(n, INT_MAX); dist[0] = 0;

C. int dist[n]; for(int i=0; i

D. std::vector<int> dist(n); dist[0] = 0;

Solution

1. Step 1: Initialize distances with maximum value

   Distances should start as infinity (INT_MAX) except source which is 0.

2. Step 2: Check code correctness

   std::vector<int> dist(n, INT_MAX); dist[0] = 0; correctly sets all distances to INT_MAX and source distance to 0.

3. Final Answer:

   std::vector<int> dist(n, INT_MAX); dist[0] = 0; -> Option B

4. Quick Check:

   Distance init = INT_MAX except source 0 [OK]

Hint: Initialize all distances to INT_MAX except source 0 [OK]

Common Mistakes:

• Setting source distance to INT_MAX
• Initializing distances to zero
• Not using vector or uninitialized array

3. Consider the following DAG with edges and weights:
0 -> 1 (2), 0 -> 2 (4), 1 -> 2 (1), 1 -> 3 (7), 2 -> 3 (3)
Using topological order starting from vertex 0, what is the shortest distance to vertex 3?

medium

A. 6

B. 7

C. 9

D. 10

Solution

1. Step 1: Find topological order and initialize distances

   Topological order: 0, 1, 2, 3. Initialize dist[0]=0, others = 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[3]=min(9, 3+3=6)=6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest path to 3 = 6 [OK]

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

Common Mistakes:

• Not updating dist[2] to 3 via vertex 1
• Ignoring relaxation from vertex 2 to 3
• Using wrong topological order

4. The following code snippet attempts to find shortest paths in a DAG but produces incorrect results. What is the bug?

std::vector<int> dist(n, INT_MAX);
dist[source] = 0;
for (int u : topoOrder) {
  for (auto &edge : graph[u]) {
    int v = edge.first, w = edge.second;
    if (dist[v] > dist[u] + w) {
      dist[v] = dist[u] + w;
    }
  }
}

medium

A. The distance array is not initialized properly.

B. The graph edges are not relaxed in topological order.

C. The source vertex distance is not set to zero.

D. The code does not check if dist[u] is INT_MAX before adding w.

Solution

1. Step 1: Analyze relaxation condition

   The code adds w to dist[u] without checking if dist[u] is INT_MAX, causing overflow.

2. Step 2: Identify missing check

   Before relaxing edges, must check dist[u] != INT_MAX to avoid invalid addition.

3. Final Answer:

   The code does not check if dist[u] is INT_MAX before adding w. -> Option D

4. Quick Check:

   Check dist[u] != INT_MAX before relaxation [OK]

Hint: Always check dist[u] != INT_MAX before adding edge weight [OK]

Common Mistakes:

• Assuming initialization is wrong
• Thinking topological order is incorrect
• Forgetting to set source distance

5. Given a DAG with vertices 0 to 4 and edges:
0->1(3), 0->2(6), 1->2(4), 1->3(4), 2->3(8), 3->4(2)
Using topological order, what is the shortest path distance from vertex 0 to vertex 4?

hard

A. 13

B. 11

C. 9

D. 14

Solution

1. Step 1: Determine topological order and initialize distances

   Topological order: 0,1,2,3,4. Initialize dist[0]=0, others = infinity.

2. Step 2: Relax edges in order

   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[3]=min(7,6+8=14)=7
   From 3: dist[4]=7+2=9

3. Final Answer:

   9 -> Option C

4. Quick Check:

   Shortest path to 4 = 9 [OK]

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

Common Mistakes:

• Not updating dist[3] correctly
• Choosing longer path via vertex 2
• Misordering topological sort