Shortest Path in DAG Using Topological Order in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with infinity values.

DSA Go

dist := make([]int, V)
for i := 0; i < V; i++ {
    dist[i] = [1]
}

Drag options to blanks, or click blank then click option'

A-1

B0

Cmath.MaxInt32

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing distances with 0 causes incorrect shortest path calculations.

Using negative numbers for initial distances.

We initialize distances with a very large number (infinity) to represent unreachable nodes initially.

2fill in blank

medium

Complete the code to update the distance of adjacent nodes during relaxation.

DSA Go

for _, edge := range graph[u] {
    v := edge.to
    weight := edge.weight
    if dist[u] != [1] && dist[u]+weight < dist[v] {
        dist[v] = dist[u] + weight
    }
}

Drag options to blanks, or click blank then click option'

A0

Bmath.MaxInt32

C-1

Ddist[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Not checking if dist[u] is infinity causes incorrect updates.

Using 0 instead of infinity in the condition.

We check if dist[u] is not infinity before relaxing edges to avoid invalid updates.

3fill in blank

hard

Fix the error in the topological sort function to correctly mark nodes as visited.

DSA Go

func topoSort(u int, visited []bool, stack *[]int, graph [][]Edge) {
    visited[u] = [1]
    for _, edge := range graph[u] {
        v := edge.to
        if !visited[v] {
            topoSort(v, visited, stack, graph)
        }
    }
    *stack = append(*stack, u)
}

Drag options to blanks, or click blank then click option'

Anil

Bfalse

C0

Dtrue

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited[u] as false causes infinite loops.

Not marking visited[u] at all.

Marking the node as true means it is visited, preventing revisiting it.

4fill in blank

hard

Fill both blanks to correctly initialize the distance of the source node and iterate over the topological order.

DSA Go

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

Drag options to blanks, or click blank then click option'

Asource

B0

Ci

Dlen(stack)

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of source for distance initialization.

Using len(stack) instead of i to index stack.

Set distance of source to 0 and use index i to access nodes in topological order.

5fill in blank

hard

Fill all three blanks to create the Edge struct, define the graph, and declare the stack for topological sort.

DSA Go

type [1] struct {
    to int
    weight int
}

graph := make([][][2], V)
stack := make([][3], 0)

Drag options to blanks, or click blank then click option'

AEdge

Cint

DNode

Attempts:

3 left

💡 Hint

Common Mistakes

Using Node instead of Edge for struct or graph.

Declaring graph as slice of int instead of Edge.

Edge struct defines graph edges; graph is a slice of Edge slices; stack holds ints for node order.

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