Shortest Path in DAG Using Topological Order in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of shortest path distances in DAG

What is the output of the following C# code that finds shortest paths from node 0 in a DAG using topological order?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int V = 6;
        List<(int, int)>[] graph = new List<(int, int)>[V];
        for (int i = 0; i < V; i++) graph[i] = new List<(int, int)>();
        graph[0].Add((1, 5));
        graph[0].Add((2, 3));
        graph[1].Add((3, 6));
        graph[1].Add((2, 2));
        graph[2].Add((4, 4));
        graph[2].Add((5, 2));
        graph[2].Add((3, 7));
        graph[3].Add((4, -1));
        graph[4].Add((5, -2));

        int[] dist = new int[V];
        for (int i = 0; i < V; i++) dist[i] = int.MaxValue;
        dist[0] = 0;

        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[V];

        void TopoSort(int u) {
            visited[u] = true;
            foreach (var (v, w) in graph[u]) {
                if (!visited[v]) TopoSort(v);
            }
            stack.Push(u);
        }

        for (int i = 0; i < V; i++) if (!visited[i]) TopoSort(i);

        while (stack.Count > 0) {
            int u = stack.Pop();
            if (dist[u] != int.MaxValue) {
                foreach (var (v, w) in graph[u]) {
                    if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
                }
            }
        }

        for (int i = 0; i < V; i++) {
            if (dist[i] == int.MaxValue) Console.Write("INF ");
            else Console.Write(dist[i] + " ");
        }
    }
}

A 0 5 3 9 7 5

B 0 5 3 9 8 6

C 0 5 3 13 7 5

D 0 5 3 10 7 5

💡 Hint

Trace the topological order and update distances carefully for each edge.

The code performs a topological sort and then relaxes edges in order. The shortest distances from node 0 are: 0 (start), 5 (0->1), 3 (0->2), 9 (0->2->3 or 0->1->3), 7 (0->2->4 or 0->2->3->4), 5 (0->2->5 or 0->2->4->5).

🧠 Conceptual

intermediate

Why use topological order for shortest path in DAG?

Why is topological order used to find shortest paths in a Directed Acyclic Graph (DAG)?

A Because it ensures nodes are processed after all their dependencies, allowing correct distance updates without cycles.

B Because it sorts nodes by their distance values automatically.

C Because it detects cycles in the graph to avoid infinite loops.

D Because it uses breadth-first search to find shortest paths.

💡 Hint

Think about how processing nodes in order affects distance calculation.

Topological order processes nodes only after all nodes leading to them are processed, so shortest distances can be updated correctly without revisiting nodes or cycles.

🔧 Debug

advanced

Identify the bug in shortest path code for DAG

What error will this C# code produce when finding shortest paths in a DAG using topological order?

DSA C#

int V = 4;
List<(int, int)>[] graph = new List<(int, int)>[V];
for (int i = 0; i < V; i++) graph[i] = new List<(int, int)>();
graph[0].Add((1, 1));
graph[1].Add((2, 2));
graph[2].Add((3, 3));

int[] dist = new int[V];
for (int i = 0; i < V; i++) dist[i] = int.MaxValue;
dist[0] = 0;

Stack<int> stack = new Stack<int>();
bool[] visited = new bool[V];

void TopoSort(int u) {
    visited[u] = true;
    foreach (var (v, w) in graph[u]) {
        if (!visited[v]) TopoSort(v);
    }
    stack.Push(u);
}

for (int i = 0; i < V; i++) TopoSort(i);

while (stack.Count > 0) {
    int u = stack.Pop();
    if (dist[u] != int.MaxValue) {
        foreach (var (v, w) in graph[u]) {
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }
}

Console.WriteLine(string.Join(" ", dist));

A Runtime error: NullReferenceException

B Output: 0 1 3 6

C Compilation error due to missing semicolon

D StackOverflowException due to infinite recursion in TopoSort

💡 Hint

Check how TopoSort is called for each node without checking if visited.

The code calls TopoSort on every node without checking if it was visited, causing infinite recursion and StackOverflowException.

❓ Predict Output

advanced

Shortest path distances with negative weights in DAG

What is the output of this C# code that finds shortest paths in a DAG with some negative edge weights?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int V = 5;
        List<(int, int)>[] graph = new List<(int, int)>[V];
        for (int i = 0; i < V; i++) graph[i] = new List<(int, int)>();
        graph[0].Add((1, 2));
        graph[0].Add((2, 3));
        graph[1].Add((3, 4));
        graph[2].Add((3, -2));
        graph[3].Add((4, 2));

        int[] dist = new int[V];
        for (int i = 0; i < V; i++) dist[i] = int.MaxValue;
        dist[0] = 0;

        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[V];

        void TopoSort(int u) {
            visited[u] = true;
            foreach (var (v, w) in graph[u]) {
                if (!visited[v]) TopoSort(v);
            }
            stack.Push(u);
        }

        for (int i = 0; i < V; i++) if (!visited[i]) TopoSort(i);

        while (stack.Count > 0) {
            int u = stack.Pop();
            if (dist[u] != int.MaxValue) {
                foreach (var (v, w) in graph[u]) {
                    if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
                }
            }
        }

        for (int i = 0; i < V; i++) {
            if (dist[i] == int.MaxValue) Console.Write("INF ");
            else Console.Write(dist[i] + " ");
        }
    }
}

A 0 2 3 1 5

B 0 2 3 1 3

C 0 2 3 -2 0

D 0 2 3 2 4

💡 Hint

Consider how negative edges affect shortest path updates in topological order.

The shortest path to node 3 is via node 2 with weight 3 + (-2) = 1. Then node 4 is reached from node 3 with +2 = 3.

🧠 Conceptual

expert

Why can't Dijkstra's algorithm be used directly on DAG with negative edges?

Why is Dijkstra's algorithm not suitable for finding shortest paths in a DAG that contains negative edge weights?

A Because Dijkstra's algorithm requires topological sorting first.

B Because DAGs always have cycles, which Dijkstra cannot handle.

C Because Dijkstra's algorithm assumes all edge weights are non-negative to guarantee correct shortest paths.

D Because Dijkstra's algorithm only works on undirected graphs.

💡 Hint

Think about how negative weights affect the greedy choice in Dijkstra's algorithm.

Dijkstra's algorithm assumes no negative edges because it greedily picks the closest node, which can fail if a shorter path appears later due to negative edges.

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