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 values.

DSA C#

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

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

A0

B-1

Cint.MaxValue

D1

Attempts:

3 left

💡 Hint

Common Mistakes

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

Using negative values can cause logic errors.

We use int.MaxValue to represent infinity for initial distances.

2fill in blank

medium

Complete the code to set the source vertex distance to zero.

DSA C#

dist[[1]] = 0;

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

Asource

B1

CV

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting distance of vertex 0 instead of the source vertex.

Using a fixed number instead of the source variable.

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

3fill in blank

hard

Fix the error in the loop that relaxes edges after topological sorting.

DSA C#

foreach (int u in topoOrder) {
    if (dist[u] != [1]) {
        foreach (var edge in graph[u]) {
            int v = edge.Item1;
            int weight = edge.Item2;
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
            }
        }
    }
}

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

Anull

B0

C-1

Dint.MaxValue

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for zero instead of infinity.

Using null which is invalid for int type.

We check if the distance is not infinity before relaxing edges to avoid invalid calculations.

4fill in blank

hard

Fill both blanks to correctly perform relaxation of edges in the shortest path algorithm.

DSA C#

foreach (var edge in graph[[1]]) {
    int v = edge.[2];
    int weight = edge.Item2;
    if (dist[v] > dist[u] + weight) {
        dist[v] = dist[u] + weight;
    }
}

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

Au

BItem1

CItem2

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'v' instead of 'u' for the graph index.

Using Item2 instead of Item1 for the adjacent vertex.

The variable u is the current vertex, and Item1 is the adjacent vertex in the edge tuple.

5fill in blank

hard

Fill all three blanks to create a dictionary of shortest distances for vertices reachable from source.

DSA C#

var shortestPaths = new Dictionary<int, int> {
    { [1], [2] }
};

for (int i = 0; i < V; i++) {
    if (dist[i] != [3] && i != [1]) {
        shortestPaths[i] = dist[i];
    }
}

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

Asource

Bdist[source]

Cint.MaxValue

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of source for the key.

Checking for zero instead of int.MaxValue for unreachable vertices.

We start the dictionary with the source vertex and its distance zero, and add other reachable vertices with distances not equal to infinity.

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 sorts edges by weight.

B. It guarantees the graph has cycles.

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

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 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 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 C

4. Quick Check:

   Topological order = linear processing [OK]

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

Common Mistakes:

• Thinking topological order works with cycles
• Confusing shortest path with longest path
• Assuming edges are sorted by weight

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 = new int[5]; for(int i = 0; i < 5; i++) dist[i] = int.MaxValue;

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

C. int[] dist = new int[5]; dist.Fill(int.MaxValue);

D. int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = 0;

Solution

1. Step 1: Understand distance initialization

   Distances should start as infinity (int.MaxValue) except the source, to represent unknown paths.

2. Step 2: Check code correctness

   int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = int.MaxValue; correctly sets all distances to int.MaxValue using a loop. int[] dist = new int[5] {0, 0, 0, 0, 0}; sets all to zero, which is incorrect. int[] dist = new int[5]; dist.Fill(int.MaxValue); uses a non-existent Fill method. int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = 0; sets all to zero, which is wrong.

3. Final Answer:

   int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = int.MaxValue; -> Option A

4. Quick Check:

   Initialize distances to max value [OK]

Hint: Initialize distances with int.MaxValue except source [OK]

Common Mistakes:

• Setting all distances to zero
• Using non-existent array methods
• Not initializing distances before algorithm

3. Consider the following DAG with edges and weights:
0 -> 1 (2), 0 -> 2 (4), 1 -> 2 (1), 1 -> 3 (7), 2 -> 4 (3), 3 -> 4 (1)
If we run the shortest path algorithm from vertex 0 using topological order, what is the shortest distance to vertex 4?

medium

A. 10

B. 6

C. 7

D. 9

Solution

1. Step 1: Find topological order and initialize distances

   Topological order can be [0,1,2,3,4]. 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[4]=3+3=6.
   From 3: dist[4]=min(6,9+1=10)=6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Shortest distance to 4 = 6 [OK]

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

Common Mistakes:

• Not updating distances after relaxation
• Using wrong topological order
• Ignoring better paths through intermediate nodes

4. The following C# code attempts to find shortest paths in a DAG but has a bug:

int[] dist = new int[V];
for(int i = 0; i < V; i++) dist[i] = int.MaxValue;
dist[source] = 0;
foreach(int u in topologicalOrder)
{
  foreach(var edge in graph[u])
  {
    int v = edge.Item1;
    int weight = edge.Item2;
    if(dist[u] + weight < dist[v])
      dist[v] = dist[u] + weight;
  }
}

What is the bug in this code?

medium

A. No check if dist[u] is int.MaxValue before adding weight

B. Edges are not relaxed in correct order

C. topologicalOrder is not computed

D. dist array is not initialized to int.MaxValue

Solution

1. Step 1: Analyze distance update condition

   The code adds dist[u] + weight without checking if dist[u] is int.MaxValue, which can cause overflow.

2. Step 2: Identify missing check

   Before adding weight, code should check if dist[u] != int.MaxValue to avoid invalid calculations.

3. Final Answer:

   No check if dist[u] is int.MaxValue before adding weight -> Option A

4. Quick Check:

   Check dist[u] before adding weight [OK]

Hint: Check dist[u] != int.MaxValue before adding weight [OK]

Common Mistakes:

• Ignoring overflow from adding to int.MaxValue
• Assuming topological order is always computed
• Thinking initialization is missing

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

hard

A. 10

B. 9

C. 7

D. 5

Solution

1. Step 1: Determine topological order and initialize distances

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

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 edge weights
• Not updating distances after better path found
• Wrong topological order causing incorrect results