Shortest Path in DAG Using Topological Order in DSA Go

Mental Model

We find the shortest path in a graph with no cycles by visiting nodes in an order where all edges go forward. This way, we update shortest distances step by step without going back.

Analogy: Imagine a line of dominoes set up so each domino can only knock down the next ones ahead, never the ones behind. By pushing dominoes in order, you know exactly how far the push travels without confusion.

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

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

Dry Run Walkthrough

Input: Graph edges with weights: 0->1(2), 0->2(4), 1->2(1), 1->3(7), 2->4(3), 4->3(2); 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 -> 1 -> 2 -> 4 -> 3

Why: We need to process nodes so all edges go forward to update shortest paths correctly

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: From 0, edges to 1 and 2 update their distances

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

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

Why: From 1, edge to 2 improves dist[2], edge to 3 sets dist[3]

Step 5: Process node 2: update dist[4]=3+3=6

dist: [0, 2, 3, 9, 6]

Why: From 2, edge to 4 updates dist[4]

Step 6: Process node 4: update dist[3]=min(9, 6+2=8)=8

dist: [0, 2, 3, 8, 6]

Why: From 4, edge to 3 improves dist[3]

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

dist: [0, 2, 3, 8, 6]

Why: No edges to update from 3

Result:

Final shortest distances: 0:0 -> 1:2 -> 2:3 -> 4:6 -> 3:8

Annotated Code

DSA Go

package main

import (
	"fmt"
	"math"
)

type Edge struct {
	to, weight int
}

func shortestPathDAG(n int, graph [][]Edge, start int) []int {
	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[start] = 0

	// Compute in-degree for topological sort
	inDegree := make([]int, n)
	for u := 0; u < n; u++ {
		for _, e := range graph[u] {
			inDegree[e.to]++
		}
	}

	// Queue for nodes with zero in-degree
	queue := []int{}
	for i := 0; i < n; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	// Process nodes in topological order
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		// Relax edges from u
		for _, e := range graph[u] {
			if dist[u] != math.MaxInt32 && dist[u]+e.weight < dist[e.to] {
				dist[e.to] = dist[u] + e.weight
			}

			inDegree[e.to]--
			if inDegree[e.to] == 0 {
				queue = append(queue, e.to)
			}
		}
	}

	return dist
}

func main() {
	n := 5
	graph := make([][]Edge, n)
	graph[0] = []Edge{{1, 2}, {2, 4}}
	graph[1] = []Edge{{2, 1}, {3, 7}}
	graph[2] = []Edge{{4, 3}}
	graph[4] = []Edge{{3, 2}}

	start := 0
	dist := shortestPathDAG(n, graph, start)

	for i, d := range dist {
		if d == math.MaxInt32 {
			fmt.Printf("Node %d: unreachable\n", i)
		} else {
			fmt.Printf("Node %d: %d\n", i, d)
		}
	}
}

dist := make([]int, n) for i := range dist { dist[i] = math.MaxInt32 } dist[start] = 0

Initialize distances with infinity except start node zero

for u := 0; u < n; u++ { for _, e := range graph[u] { inDegree[e.to]++ } }

Calculate in-degree for each node to find start points

for i := 0; i < n; i++ { if inDegree[i] == 0 { queue = append(queue, i) } }

Add nodes with zero in-degree to queue for topological order

for len(queue) > 0 { u := queue[0] queue = queue[1:]

Process nodes in topological order by removing from queue

for _, e := range graph[u] { if dist[u] != math.MaxInt32 && dist[u]+e.weight < dist[e.to] { dist[e.to] = dist[u] + e.weight }

Relax edges: update shortest distance if better path found

inDegree[e.to]-- if inDegree[e.to] == 0 { queue = append(queue, e.to) }

Decrease in-degree and add to queue if zero for next processing

Output

Node 0: 0

Node 1: 2

Node 2: 3

Node 3: 8

Node 4: 6

Complexity Analysis

Time: O(V + E) because each node and edge is processed once in topological order

Space: O(V + E) for storing graph and auxiliary arrays like distance and in-degree

vs Alternative: Compared to Dijkstra's algorithm, this is faster for DAGs because no priority queue is needed and no cycles to worry about

Edge Cases

Graph with no edges

Distances remain infinity except start node zero

DSA Go

dist[start] = 0

Graph with unreachable nodes

Unreachable nodes keep distance infinity and print 'unreachable'

DSA Go

if d == math.MaxInt32 { fmt.Printf("Node %d: unreachable\n", i) }

Single node graph

Distance to start node is zero, no edges to process

DSA Go

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 update distances efficiently.

Common Mistakes

Mistake: Not initializing distances to infinity except start node
Fix: Set all distances to max int and start node distance to zero before processing

Mistake: Not updating in-degree correctly leading to wrong topological order
Fix: Decrease in-degree after processing edges and add nodes with zero in-degree to queue

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 insight is that topological order ensures all edges go forward, so distances can be updated once per node.

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 finds the longest path instead of the shortest.

B. It guarantees the graph has cycles.

C. It sorts vertices by their weights.

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

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 means each vertex is processed after all its predecessors, so shortest paths can be updated without revisiting.

3. Final Answer:

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

4. Quick Check:

   Topological order = linear processing without revisits [OK]

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

Common Mistakes:

• Thinking topological order applies to graphs with cycles
• Confusing topological order with sorting by weights
• Assuming it finds longest path by default

2. Which Go code snippet correctly initializes the distance array for shortest path calculation in a DAG with 5 vertices, starting from vertex 0?

easy

A. dist := make([]int, 5); for i := range dist { dist[i] = 1<<31 - 1 }; dist[0] = 0

B. dist := make([]int, 5); for i := range dist { dist[i] = 0 }; dist[0] = 1<<31 - 1

C. dist := make([]int, 5); for i := range dist { dist[i] = -1 }; dist[0] = 0

D. dist := make([]int, 5); dist[0] = 0

Solution

1. Step 1: Initialize distances with max int

   We set all distances to a large number (infinity) to represent unknown paths, here 1<<31 - 1 for max int.

2. Step 2: Set source distance to zero

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

3. Final Answer:

   dist := make([]int, 5); for i := range dist { dist[i] = 1<<31 - 1 }; dist[0] = 0 -> Option A

4. Quick Check:

   Initialize with max int, source zero [OK]

Hint: Set all distances max int, source distance zero [OK]

Common Mistakes:

• Setting all distances to zero initially
• Not setting source distance to zero
• Using -1 as initial distance

3. Given the following DAG edges with weights: 0->1 (2), 0->2 (4), 1->2 (1), 1->3 (7), 2->3 (3). What is the shortest distance array from source vertex 0 after running shortest path using topological order?

dist := []int{0, 2147483647, 2147483647, 2147483647}
// After processing edges in topological order

medium

A. [0, 4, 5, 8]

B. [0, 2, 4, 7]

C. [0, 2, 3, 6]

D. [0, 3, 4, 7]

Solution

1. Step 1: Relax edges from source 0

   dist[1] = min(inf, 0+2) = 2; dist[2] = min(inf, 0+4) = 4

2. Step 2: Relax edges from vertex 1 and 2

   From 1: dist[2] = min(4, 2+1) = 3; dist[3] = min(inf, 2+7) = 9
   From 2: dist[3] = min(9, 3+3) = 6

3. Final Answer:

   [0, 2, 3, 6] -> Option C

4. Quick Check:

   Relax edges in topological order = [0,2,3,6] [OK]

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

Common Mistakes:

• Not updating dist[2] to 3 after relaxing from vertex 1
• Ignoring relaxation from vertex 2 to 3
• Using initial distances without updates

4. Consider this Go code snippet for shortest path in DAG:

dist := make([]int, 4)
for i := range dist {
    dist[i] = 1<<31 - 1
}
dist[0] = 0
for _, u := range topoOrder {
    for _, edge := range graph[u] {
        if dist[u]+edge.weight < dist[edge.to] {
            dist[edge.to] = dist[u] + edge.weight
        }
    }
}

If the graph contains a cycle, what problem will occur?

medium

A. The code will produce correct shortest paths regardless.

B. The code will skip some vertices but finish normally.

C. The code will run infinitely because topological order is invalid.

D. The code will panic due to nil pointer dereference.

Solution

1. Step 1: Understand topological order requirement

   Topological order exists only if the graph has no cycles. If a cycle exists, topoOrder is invalid or partial.

2. Step 2: Effect of cycle on code execution

   Standard topological sort algorithms produce a partial order (not all vertices included), so the loop will skip some vertices but finish normally since topoOrder is a finite slice.

3. Final Answer:

   The code will skip some vertices but finish normally. -> Option B

4. Quick Check:

   Cycle causes partial topoOrder, skips vertices [OK]

Hint: DAG must be acyclic; cycles break topological order [OK]

Common Mistakes:

• Assuming code works fine with cycles
• Expecting panic instead of infinite loop
• Ignoring the need for cycle detection

5. You have a DAG with 6 vertices and weighted 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. 5

B. 4

C. 3

D. 7

Solution

1. Step 1: Initialize distances

   dist = [0, inf, inf, inf, inf, inf]

2. Step 2: Relax edges in topological 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
   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
   From 4: dist[5]=min(5,7+(-2)=5)=5

3. Step 3: Check final distance to vertex 5

   dist[5] = 5

4. Final Answer:

   5 -> Option A

5. Quick Check:

   Relax edges carefully to get dist[5] = 5 [OK]

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

Common Mistakes:

• Ignoring negative edge weights
• Not updating distances after relaxation
• Assuming negative weights cause cycles