Shortest Path in DAG Using Topological Order in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with infinity.

DSA C++

vector<int> dist(V, [1]);

Drag options to blanks, or click blank then click option'

AINT_MAX

B0

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of INT_MAX causes incorrect shortest path calculations.

We initialize distances with INT_MAX to represent infinity before relaxation.

2fill in blank

medium

Complete the code to relax edges in the topological order loop.

DSA C++

for (auto it : adj[u]) {
    int v = it.first;
    int weight = it.second;
    if (dist[u] != INT_MAX && dist[u] + weight [1] dist[v]) {
        dist[v] = dist[u] + weight;
    }
}

Drag options to blanks, or click blank then click option'

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < causes no updates to shorter paths.

We update dist[v] only if the new path is shorter, so we check if dist[u] + weight < dist[v].

3fill in blank

hard

Fix the error in the topological sort DFS function to mark nodes as visited.

DSA C++

void topoSort(int node, vector<bool> &visited, stack<int> &st, vector<pair<int,int>> adj[]) {
    visited[node] = [1];
    for (auto it : adj[node]) {
        if (!visited[it.first]) {
            topoSort(it.first, visited, st, adj);
        }
    }
    st.push(node);
}

Drag options to blanks, or click blank then click option'

Afalse

B1

Ctrue

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited[node] as false causes infinite recursion.

Marking the node as true means it is visited to avoid revisiting.

4fill in blank

hard

Fill both blanks to complete the loop that processes nodes in topological order and relaxes edges.

DSA C++

while (!st.empty()) {
    int u = st.top();
    st.pop();
    if (dist[u] != INT_MAX) {
        for (auto it : adj[u]) {
            int v = it.[1];
            int weight = it.[2];
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

Afirst

Bsecond

Csize

Dempty

Attempts:

3 left

💡 Hint

Common Mistakes

Using .size or .empty causes compilation errors.

Each adjacency list element is a pair where first is the node and second is the weight.

5fill in blank

hard

Fill the blanks to initialize the graph, perform topological sort, and compute shortest paths.

DSA C++

int V = [1];
vector<pair<int,int>> adj[V];
// Add edges
adj[0].push_back({1, 5});
adj[0].push_back({2, 3});
vector<bool> visited(V, false);
stack<int> st;
for (int i = 0; i < V; i++) {
    if (!visited[i]) {
        topoSort(i, visited, st, adj);
    }
}
vector<int> dist(V, INT_MAX);
dist[[2]] = 0;
// Relax edges
while (!st.empty()) {
    int u = st.top();
    st.pop();
    if (dist[u] != INT_MAX) {
        for (auto it : adj[u]) {
            int v = it.first;
            int weight = it.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
}
cout << "Shortest distances from source:" << endl;
for (int i = 0; i < V; i++) {
    cout << i << " -> " << dist[i] << endl;
}

Drag options to blanks, or click blank then click option'

A3

B0

C1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Wrong vertex count causes out-of-range errors.

Wrong source index causes incorrect distances.

We set V=3 for 3 nodes, source node as 0.

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