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

Shortest Path in DAG Using Topological Order

📖 Scenario: You are working on a project to find the shortest path distances from a starting point to all other points in a network that has no cycles (a Directed Acyclic Graph or DAG). This is useful in scheduling tasks or planning routes where some steps must happen before others.

🎯 Goal: Build a Go program that finds the shortest path distances from a given source node to all other nodes in a DAG using topological order.

📋 What You'll Learn

Create a graph as an adjacency list with exact edges and weights

Create a variable to hold the number of nodes

Implement topological sorting using DFS

Use the topological order to find shortest paths from the source node

Print the shortest distances array

💡 Why This Matters

🌍 Real World

Finding shortest paths in DAGs is useful in project scheduling, task ordering, and route planning where some tasks must happen before others.

💼 Career

Understanding topological sorting and shortest path algorithms is important for software engineers working on compilers, build systems, and optimization problems.

1

Create the graph data structure

Create a variable called graph as a slice of slices of pairs representing edges and weights for 6 nodes. Use this exact graph:
graph[0] = []Edge{{to: 1, weight: 5}, {to: 2, weight: 3}}
graph[1] = []Edge{{to: 3, weight: 6}, {to: 2, weight: 2}}
graph[2] = []Edge{{to: 4, weight: 4}, {to: 5, weight: 2}, {to: 3, weight: 7}}
graph[3] = []Edge{{to: 4, weight: -1}}
graph[4] = []Edge{{to: 5, weight: -2}}
graph[5] = []Edge{}

DSA Go

package main

type Edge struct {
    to     int
    weight int
}

func main() {
    // Create the graph variable with 6 nodes and edges
    // Your code here
}

Hint

Use make([][]Edge, 6) to create the graph slice for 6 nodes. Then assign each node's edges exactly as shown.

2

Create variables for topological sort

Create a variable called visited as a slice of bool with length 6 to track visited nodes, and a variable called stack as a slice of int to store the topological order.

DSA Go

package main

type Edge struct {
    to     int
    weight int
}

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

    // Create visited slice and stack slice
    // Your code here
}

Hint

Use make([]bool, 6) for visited and declare stack as var stack []int.

3

Implement topological sort and shortest path logic

Write a function called dfs that takes node int, graph [][]Edge, visited []bool, and stack *[]int. It should mark node visited, call dfs recursively on unvisited neighbors, then append node to *stack. Then in main, run dfs for all nodes 0 to 5 if not visited. Next, create a slice dist of length 6 with all values set to 1<<31 - 1 (max int). Set dist[0] = 0. Finally, process nodes in reverse order from stack to relax edges and update dist with shortest distances.

DSA Go

package main

type Edge struct {
    to     int
    weight int
}

func dfs(node int, graph [][]Edge, visited []bool, stack *[]int) {
    // Your code here
}

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

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

    // Run dfs for all nodes
    // Create dist slice and set dist[0] = 0
    // Relax edges in topological order
    // Your code here
}

Hint

Use DFS to fill stack with nodes in topological order. Then initialize dist with max int values except source 0. Relax edges in reverse topological order.

4

Print the shortest distances

Print the dist slice to show shortest distances from node 0 to all nodes.

DSA Go

package main

type Edge struct {
    to     int
    weight int
}

func dfs(node int, graph [][]Edge, visited []bool, stack *[]int) {
    visited[node] = true
    for _, edge := range graph[node] {
        if !visited[edge.to] {
            dfs(edge.to, graph, visited, stack)
        }
    }
    *stack = append(*stack, node)
}

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

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

    for i := 0; i > 1)
    for i := range dist {
        dist[i] = maxInt
    }
    dist[0] = 0

    for i := len(stack) - 1; i >= 0; i-- {
        node := stack[i]
        if dist[node] != maxInt {
            for _, edge := range graph[node] {
                if dist[node]+edge.weight < dist[edge.to] {
                    dist[edge.to] = dist[node] + edge.weight
                }
            }
        }
    }

    // Print the dist slice
    // Your code here
}

Hint

Use fmt.Println(dist) to print the shortest distances slice.

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