Shortest Path in DAG Using Topological Order in DSA C#

Mental Model

We find the shortest path in a graph with no cycles by visiting nodes in order so all dependencies come first. Then we update shortest distances step by step.

Analogy: Imagine tasks that depend on others. You finish tasks in order so all needed tasks are done before starting the next. This order helps find the quickest way to finish all tasks.

Graph (DAG):
0 -> 1 -> 3
 ↓    ↓
 2 -> 4

Topological order: 0 -> 2 -> 1 -> 4 -> 3

Dry Run Walkthrough

Input: Graph edges with weights: 0->1(2), 0->2(4), 1->3(7), 1->4(3), 2->4(5); start node: 0

Goal: Find shortest distances from node 0 to all others using topological order

Step 1: Find topological order of nodes

Topological order: 0 -> 2 -> 1 -> 4 -> 3

Why: We must process nodes so all edges go from earlier to later nodes

Step 2: Initialize distances: dist[0]=0, others=∞

dist: [0, ∞, ∞, ∞, ∞]

Why: Start node distance is zero, others unknown

Step 3: Process node 0: update dist[1]=2, dist[2]=4

dist: [0, 2, 4, ∞, ∞]

Why: Edges from 0 give new shortest distances

Step 4: Process node 2: update dist[4]=min(∞,4+5)=9

dist: [0, 2, 4, ∞, 9]

Why: Edge 2->4 updates distance if shorter

Step 5: Process node 1: update dist[3]=min(∞,2+7)=9, dist[4]=min(9,2+3)=5

dist: [0, 2, 4, 9, 5]

Why: Edges from 1 update distances if shorter

Step 6: Process node 4: no outgoing edges, distances unchanged

dist: [0, 2, 4, 9, 5]

Why: No edges to relax from node 4

Step 7: Process node 3: no outgoing edges, distances unchanged

dist: [0, 2, 4, 9, 5]

Why: No edges to relax from node 3

Result:

Final shortest distances: 0 -> 0, 1 -> 2, 2 -> 4, 3 -> 9, 4 -> 5

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    public int V;
    public List<(int, int)>[] adj;

    public Graph(int v) {
        V = v;
        adj = new List<(int, int)>[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new List<(int, int)>();
        }
    }

    public void AddEdge(int u, int v, int w) {
        adj[u].Add((v, w));
    }

    private void TopologicalSortUtil(int v, bool[] visited, Stack<int> stack) {
        visited[v] = true;
        foreach (var (nbr, _) in adj[v]) {
            if (!visited[nbr]) {
                TopologicalSortUtil(nbr, visited, stack);
            }
        }
        stack.Push(v); // push after visiting neighbors
    }

    public Stack<int> TopologicalSort() {
        bool[] visited = new bool[V];
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                TopologicalSortUtil(i, visited, stack);
            }
        }
        return stack;
    }

    public int[] ShortestPath(int start) {
        int[] dist = new int[V];
        for (int i = 0; i < V; i++) {
            dist[i] = int.MaxValue;
        }
        dist[start] = 0;

        Stack<int> stack = TopologicalSort();

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

class Program {
    static void Main() {
        Graph g = new Graph(5);
        g.AddEdge(0, 1, 2);
        g.AddEdge(0, 2, 4);
        g.AddEdge(1, 3, 7);
        g.AddEdge(1, 4, 3);
        g.AddEdge(2, 4, 5);

        int start = 0;
        int[] dist = g.ShortestPath(start);

        for (int i = 0; i < dist.Length; i++) {
            if (dist[i] == int.MaxValue) {
                Console.WriteLine($"Distance from {start} to {i} is Infinity");
            } else {
                Console.WriteLine($"Distance from {start} to {i} is {dist[i]}");
            }
        }
    }
}

stack.Push(v); // push after visiting neighbors

Add node to stack after all its descendants are processed to get topological order

dist[start] = 0;

Initialize start node distance to zero

while (stack.Count > 0) {

Process nodes in topological order

if (dist[u] != int.MaxValue) {

Only relax edges from nodes reachable from start

if (dist[u] + w < dist[v]) {

Relax edge if new distance is shorter

dist[v] = dist[u] + w; // relax edge

Update shortest distance to neighbor

Output

Distance from 0 to 0 is 0

Distance from 0 to 1 is 2

Distance from 0 to 2 is 4

Distance from 0 to 3 is 9

Distance from 0 to 4 is 5

Complexity Analysis

Time: O(V + E) because we do a topological sort (O(V+E)) and then relax each edge once

Space: O(V + E) for adjacency list and stack used in topological sort

vs Alternative: Compared to Dijkstra's algorithm (O(E log V)), this is faster for DAGs because no priority queue is needed

Edge Cases

Graph with no edges

Distances remain infinity except start node which is zero

DSA C#

dist[start] = 0;

Graph with unreachable nodes

Distances to unreachable nodes remain infinity

DSA C#

if (dist[u] != int.MaxValue) {

Single node graph

Distance to itself is zero

DSA C#

dist[start] = 0;

When to Use This Pattern

When you see a graph with no cycles and need shortest paths, use topological order to process nodes once and relax edges efficiently.

Common Mistakes

Mistake: Not performing topological sort before relaxing edges
Fix: Always get topological order first to ensure correct relaxation sequence

Mistake: Relaxing edges from nodes with infinite distance
Fix: Check if current node distance is not infinity before relaxing edges

Summary

Finds shortest paths in a directed acyclic graph by processing nodes in topological order.

Use when the graph has no cycles and you want efficient shortest path calculation.

The key is to process nodes so all edges go from processed to unprocessed nodes, allowing one pass relaxation.

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