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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of shortest path distances after topological processing

What is the output of the shortest path distances array after running the given Go code for shortest path in a DAG?

DSA Go

package main

import (
	"fmt"
	"math"
)

type Edge struct {
	to, weight int
}

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

	visited := make([]bool, n)
	var stack []int

	var dfs func(int)
	dfs = func(u int) {
		visited[u] = true
		for _, e := range edges[u] {
			if !visited[e.to] {
				dfs(e.to)
			}
		}
		stack = append(stack, u)
	}

	for i := 0; i < n; i++ {
		if !visited[i] {
			dfs(i)
		}
	}

	for i := len(stack) - 1; i >= 0; i-- {
		u := stack[i]
		if dist[u] != math.MaxInt64 {
			for _, e := range edges[u] {
				if dist[u]+e.weight < dist[e.to] {
					dist[e.to] = dist[u] + e.weight
				}
			}
		}
	}

	return dist
}

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

	start := 1
	dist := shortestPathDAG(n, edges, start)
	fmt.Println(dist)
}

A [9223372036854775807 0 2 5 4 2]

B [9223372036854775807 0 3 6 5 3]

C [9223372036854775807 0 2 7 3 1]

D [9223372036854775807 0 2 6 3 1]

💡 Hint

Trace the topological order and update distances step-by-step from the start node.

The code performs a topological sort using DFS, then relaxes edges in topological order to find shortest paths from node 1.

Starting from node 1 with distance 0, the distances to reachable nodes update as follows:

• Node 2: 2 (via edge 1->2 with weight 2)
• Node 3: 5 (via 1->2->3 with weights 2+3)
• Node 4: 4 (via 1->2->4 with weights 2+2)
• Node 5: 2 (via 1->2->5 with weights 2+0 or 1->2->4->5 with weights 2+2+(-2))

Nodes unreachable from start remain at MaxInt64 (9223372036854775807).

🧠 Conceptual

intermediate

Why does topological order help in shortest path for DAG?

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

A Because it groups nodes by their degree to optimize traversal.

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 ensures nodes are processed only after all their predecessors, allowing correct distance updates without cycles.

💡 Hint

Think about how processing order affects distance relaxation.

Topological order processes nodes so that all edges go from earlier to later nodes. This means when we relax edges, all predecessors of a node have their shortest distances computed already, ensuring correct updates without revisiting nodes.

🔧 Debug

advanced

Identify the bug causing incorrect shortest path results

Given the following Go code snippet for shortest path in DAG, which option describes the bug causing incorrect results?

DSA Go

for i := len(stack) - 1; i >= 0; i-- {
	u := stack[i]
	if dist[u] != math.MaxInt64 {
		for _, e := range edges[u] {
			if dist[u]+e.weight <= dist[e.to] {
				dist[e.to] = dist[u] + e.weight
			}
		}
	}
}

A Edges should be relaxed before the topological sort, not after.

B The loop should iterate from 0 to len(stack)-1, not backwards.

C Using '<=' instead of '<' causes unnecessary updates and may overwrite correct distances.

D The condition 'dist[u] != math.MaxInt32' should be removed to update all nodes.

💡 Hint

Check how the comparison operator affects distance updates.

The use of '<=' allows updating distances even when the new distance equals the current one, causing redundant updates and possibly incorrect paths.

Using '<' ensures updates only when a strictly shorter path is found.

📝 Syntax

advanced

Identify the syntax error in the Go code for topological sort

Which option contains the syntax error in this Go code snippet for DFS-based topological sort?

DSA Go

var dfs func(int)
dfs = func(u int) {
	visited[u] = true
	for _, e := range edges[u] {
		if !visited[e.to] {
			dfs(e.to)
		}
	}
	stack = append(stack, u)
}

A Missing closing brace '}' for the dfs function definition.

B No syntax error; the code is correct.

C Using 'var dfs func(int)' without initialization causes runtime error.

D Incorrect function declaration syntax for dfs variable.

💡 Hint

Check function declaration and braces carefully.

The code correctly declares a variable dfs of function type and assigns an anonymous function to it. The braces are balanced and syntax is valid.

🚀 Application

expert

Number of nodes reachable from start after shortest path calculation

After running shortest path in DAG from start node 0 on the graph below, how many nodes have a finite shortest distance (not infinity)? Edges: 0 -> 1 (weight 2) 0 -> 2 (weight 4) 1 -> 2 (weight 1) 1 -> 3 (weight 7) 2 -> 4 (weight 3) 3 -> 5 (weight 1) 4 -> 3 (weight 2) Start node: 0

A 6

B 4

C 5

D 3

💡 Hint

Trace reachable nodes from start using edges.

From node 0, all nodes 1, 2, 3, 4, 5 are reachable through paths:

• 0->1
• 0->2
• 0->1->3
• 0->2->4
• 0->1->3->5
• 0->2->4->3

All 6 nodes (0 to 5) have finite shortest distances.

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