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

int dist[V];
for (int i = 0; i < V; i++) {
    dist[i] = [1];
}
dist[src] = 0;

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

AINT_MAX

B-1

C0

DNULL

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of a large number causes incorrect shortest path calculation.

Using NULL is invalid for integer arrays.

We use INT_MAX to represent infinity for initial distances.

2fill in blank

medium

Complete the code to perform topological sorting using DFS.

DSA C

void topologicalSortUtil(int v, int visited[], stack<int> &Stack) {
    visited[v] = 1;
    for (auto i : adj[v]) {
        if (!visited[i.first])
            [1](i.first, visited, Stack);
    }
    Stack.push(v);
}

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

Asort

BtopologicalSort

Cdfs

DtopologicalSortUtil

Attempts:

3 left

💡 Hint

Common Mistakes

Calling a non-existent function causes compilation errors.

Using the wrong function name breaks recursion.

The function calls itself recursively to visit all adjacent vertices.

3fill in blank

hard

Fix the error in updating the distance of adjacent vertices.

DSA C

if (dist[u] != INT_MAX && dist[u] + weight < [1]) {
    dist[v] = dist[u] + weight;
}

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

Adist[v]

Bdist[u]

Cweight

DINT_MAX

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with dist[u] causes wrong updates.

Using weight alone ignores current distances.

We compare the new distance with the current distance of vertex v.

4fill in blank

hard

Fill both blanks to relax edges in topological order.

DSA C

while (!Stack.empty()) {
    int u = Stack.top();
    Stack.pop();

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

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

Aweight

Bv

Cu

Ddist[u]

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up vertex names in comparison.

Using dist[u] instead of weight in addition.

We add the edge weight to dist[u] and compare with dist[v].

5fill in blank

hard

Fill all three blanks to print the shortest distances after processing.

DSA C

for (int i = 0; i < V; i++) {
    if (dist[i] == [1])
        printf("%d: INF\n", i);
    else
        printf("%d: %d\n", [2], [3]);
}

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

AINT_MAX

Bi

Cdist[i]

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Printing wrong variables causes incorrect output.

Not checking for infinity leads to wrong distance display.

We print INF if distance is INT_MAX, else print vertex and its distance.

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 guarantees the graph has cycles.

B. It allows processing vertices in a linear order without revisiting nodes.

C. It sorts vertices by their weights.

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

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges vertices so that every directed edge goes from an earlier vertex to a later one, ensuring no cycles.

2. Step 2: Use topological order for shortest path

   Processing vertices in this order allows updating shortest distances without revisiting nodes, making the algorithm efficient.

3. Final Answer:

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

4. Quick Check:

   Topological order = linear processing [OK]

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

Common Mistakes:

• Thinking DAG has cycles
• Confusing topological order with sorting by weights
• Assuming it finds longest path by default

2. Which of the following C code snippets correctly initializes the distance array for shortest path calculation in a DAG with 5 vertices?

easy

A. int dist[5] = {0, 0, 0, 0, 0};

B. int dist[5] = {-1, -1, -1, -1, -1};

C. int dist[5]; for(int i=0; i<5; i++) dist[i] = INT_MAX;

D. int dist[5] = {INT_MIN, INT_MIN, INT_MIN, INT_MIN, INT_MIN};

Solution

1. Step 1: Understand initialization for shortest path

   Distances should start as very large values (infinity) to represent unknown paths.

2. Step 2: Identify correct initialization

   Using INT_MAX sets all distances to a large number, suitable for shortest path updates.

3. Final Answer:

   int dist[5]; for(int i=0; i<5; i++) dist[i] = INT_MAX; -> Option C

4. Quick Check:

   Initialize distances to INT_MAX [OK]

Hint: Initialize distances with INT_MAX for shortest path [OK]

Common Mistakes:

• Initializing distances to zero (wrong for shortest path)
• Using INT_MIN which is for max path, not min
• Using -1 which can cause incorrect comparisons

3. Consider the following DAG with edges and weights:
0 -> 1 (2), 0 -> 2 (4), 1 -> 2 (1), 1 -> 3 (7), 2 -> 3 (3)
If we run shortest path from vertex 0 using topological order, 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 can be [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, dist[3]=2+7=9.
   From 2: dist[3]=min(9,3+3)=6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest path to 3 = 6 [OK]

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

Common Mistakes:

• Not updating dist[2] to 3 from 1->2 edge
• Ignoring better path from 2 to 3
• Using wrong topological order

4. Given this code snippet for shortest path in DAG, what is the error?

for (int i = 0; i < V; i++) {
  for (auto edge : adj[i]) {
    int v = edge.first;
    int weight = edge.second;
    if (dist[i] + weight < dist[v])
      dist[v] = dist[i] + weight;
  }
}

Assume dist is initialized and adj is adjacency list.

medium

A. The outer loop should follow topological order, not 0 to V-1.

B. The weight variable is not assigned correctly.

C. The condition should be dist[v] + weight < dist[i].

D. The adjacency list should be reversed.

Solution

1. Step 1: Check loop order for shortest path in DAG

   The outer loop must process vertices in topological order to ensure correct relaxation.

2. Step 2: Identify the error in loop order

   Looping from 0 to V-1 may not respect topological order, causing incorrect distance updates.

3. Final Answer:

   The outer loop should follow topological order, not 0 to V-1. -> Option A

4. Quick Check:

   Use topological order for outer loop [OK]

Hint: Always loop vertices in topological order for DAG shortest path [OK]

Common Mistakes:

• Ignoring topological order in loops
• Mixing up edge weight usage
• Reversing adjacency list unnecessarily

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

hard

A. 7

B. 8

C. 4

D. 5

Solution

1. Step 1: Determine topological order and initialize distances

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

2. Step 2: Relax edges in order

   From 0: dist[1]=5, dist[2]=3.
   From 1: dist[3]=min(inf,5+6=11)=11, dist[2]=min(3,5+2=7)=3 (unchanged).
   From 2: dist[4]=min(inf,3+4=7)=7, dist[5]=min(inf,3+2=5)=5, dist[3]=min(11,3+7=10)=10.
   From 3: dist[4]=min(7,10+(-1)=9)=7 (unchanged).
   From 4: dist[5]=min(5,7+(-2)=5)=5 (unchanged).

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Shortest distance to 5 = 5 [OK]

Hint: Relax edges in topological order, watch negative weights carefully [OK]

Common Mistakes:

• Ignoring negative weights in relaxation
• Not updating distances with better paths
• Wrong topological order causing errors