Shortest Path in DAG Using Topological Order in DSA C# - Build from Scratch

Shortest Path in DAG Using Topological Order

📖 Scenario: You are working on a project that involves finding the shortest path in a Directed Acyclic Graph (DAG). This is useful in scheduling tasks where some tasks must be done before others, like planning a set of jobs with dependencies.

🎯 Goal: Build a program that finds the shortest distance from a starting node to all other nodes in a DAG using topological order.

📋 What You'll Learn

Create a graph using adjacency list representation with exact edges and weights

Create an array to store shortest distances initialized properly

Implement topological sorting using DFS

Use the topological order to relax edges and find shortest paths

Print the shortest distances from the start node to all nodes

💡 Why This Matters

🌍 Real World

Finding shortest paths in DAGs is useful in project scheduling, task ordering, and optimizing workflows where some tasks depend on others.

💼 Career

Understanding shortest path algorithms in DAGs is important for software engineers working on compilers, build systems, and workflow automation.

1

Create the graph as adjacency list

Create a variable called graph as a list of lists of tuples (int, int) with 6 nodes (0 to 5). Add these edges with weights exactly:
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).

DSA C#

// Create the graph variable and add edges with weights
// Your code here

Hint

Use an array of lists to represent the graph. Each list holds tuples of (neighbor, weight).

2

Create distance array and visited array

Create an integer array called dist of size 6 and initialize all values to int.MaxValue. Create a boolean array called visited of size 6 initialized to false. Set dist[0] to 0 as the start node distance.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List[] graph = new List[6];
        for (int i = 0; i ();

        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));

        // Create dist and visited arrays
        // Your code here
    }
}

Hint

Use a loop to set all distances to int.MaxValue except the start node which is 0.

3

Implement topological sort and shortest path logic

Create a method called TopologicalSort that takes graph, visited, stack, and node as parameters. Use DFS to mark node as visited and recursively call TopologicalSort for all unvisited neighbors. After visiting neighbors, push node onto stack. Then, in Main, create a stack of integers called stack and call TopologicalSort for all nodes from 0 to 5 if not visited. After topological sorting, pop nodes from stack and relax edges to update dist if a shorter path is found.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void TopologicalSort(List[] graph, bool[] visited, Stack stack, int node)
    {
        // Implement DFS for topological sort
        // Your code here
    }

    static void Main()
    {
        List[] graph = new List[6];
        for (int i = 0; i ();

        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[6];
        bool[] visited = new bool[6];
        for (int i = 0; i  stack = new Stack();

        // Call TopologicalSort for all nodes
        // Relax edges using topological order
        // Your code here
    }
}

Hint

Use DFS to fill the stack with nodes in topological order. Then pop nodes and update distances if a shorter path is found.

4

Print the shortest distances

Use a for loop from 0 to 5 to print the shortest distance from node 0 to each node in the format: "Distance to node X is Y". If the distance is int.MaxValue, print "Distance to node X is Infinity" instead.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void TopologicalSort(List[] graph, bool[] visited, Stack stack, int node)
    {
        visited[node] = true;
        foreach (var (neighbor, _) in graph[node])
        {
            if (!visited[neighbor])
                TopologicalSort(graph, visited, stack, neighbor);
        }
        stack.Push(node);
    }

    static void Main()
    {
        List[] graph = new List[6];
        for (int i = 0; i ();

        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[6];
        bool[] visited = new bool[6];
        for (int i = 0; i  stack = new Stack();

        for (int i = 0; i  0)
        {
            int node = stack.Pop();
            if (dist[node] != int.MaxValue)
            {
                foreach (var (neighbor, weight) in graph[node])
                {
                    if (dist[node] + weight < dist[neighbor])
                        dist[neighbor] = dist[node] + weight;
                }
            }
        }

        // Print shortest distances
        // Your code here
    }
}

Hint

Loop through the dist array and print each distance. Use a condition to print "Infinity" if the distance is int.MaxValue.

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