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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with infinity for all vertices except the source.

DSA Python

dist = [[1]] * V
source = 0

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

ANone

B0

C-1

Dfloat('inf')

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of infinity causes incorrect shortest path calculations.

Using None causes errors during comparisons.

We initialize distances to infinity to represent that initially all vertices are unreachable except the source.

2fill in blank

medium

Complete the code to perform topological sorting using DFS.

DSA Python

def topological_sort_util(v, visited, stack):
    visited[v] = True
    for i in graph[v]:
        if not visited[i[0]]:
            topological_sort_util(i[0], visited, stack)
    stack.[1](v)

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

Aappend

Bpop

Cinsert

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop removes elements instead of adding.

Using insert without index causes errors.

We append the vertex to the stack after visiting all its neighbors to maintain topological order.

3fill in blank

hard

Fix the error in the relaxation step inside the shortest path calculation.

DSA Python

for node in stack[::-1]:
    if dist[node] != float('inf'):
        for neighbor, weight in graph[node]:
            if dist[neighbor] [1] dist[node] + weight:
                dist[neighbor] = dist[node] + weight

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

A<

B>

C<=

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' causes no updates and wrong shortest paths.

Using '>=' may cause unnecessary updates.

Relaxation updates the distance if the new path is shorter, so we check if current distance is greater than new path.

4fill in blank

hard

Fill both blanks to complete the initialization and topological sort call.

DSA Python

visited = [[1]] * V
stack = []
for i in range(V):
    if not visited[i]:
        topological_sort_util(i, visited, [2])

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

AFalse

BTrue

Cstack

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing visited with True causes skipping all nodes.

Passing visited instead of stack causes errors.

We initialize visited with False and pass stack to collect topological order.

5fill in blank

hard

Fill all three blanks to complete the shortest path function using topological order.

DSA Python

def shortest_path(graph, V, source):
    dist = [float('inf')] * V
    dist[[1]] = 0
    visited = [False] * V
    stack = []
    for i in range(V):
        if not visited[i]:
            topological_sort_util(i, visited, stack)
    for node in stack[[2]]:
        if dist[node] != float('inf'):
            for neighbor, weight in graph[node]:
                if dist[neighbor] > dist[node] + [3]:
                    dist[neighbor] = dist[node] + weight
    return dist

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

Asource

B::-1

Cweight

Dsource + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Not reversing stack causes incorrect order processing.

Using wrong index for source distance initialization.

Using wrong variable instead of weight in relaxation.

Set distance of source to 0, process nodes in reverse topological order, and use edge weight for 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 allows processing vertices in a linear order without revisiting nodes.

B. It guarantees the graph has cycles.

C. It sorts the graph by edge weights.

D. It finds the longest path instead of the shortest.

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges nodes so all edges go from earlier to later nodes, ensuring no cycles.

2. Step 2: Use topological order for shortest path

   Processing nodes in this order means each node is visited once, and distances can be updated efficiently without revisiting.

3. Final Answer:

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

4. Quick Check:

   Topological order = linear processing [OK]

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

Common Mistakes:

• Thinking topological order applies to graphs with cycles
• Confusing shortest path with longest path
• Assuming topological order sorts by edge weights

2. Which of the following Python code snippets correctly initializes the distance array for shortest path calculation in a DAG with 5 nodes, starting from node 0?

easy

A. dist = [float('inf')] * 5; dist[5] = 0

B. dist = [0] * 5; dist[0] = float('inf')

C. dist = [None] * 5; dist[0] = 0

D. dist = [float('inf')] * 5; dist[0] = 0

Solution

1. Step 1: Initialize distances with infinity

   We set all distances to infinity to represent unknown paths initially.

2. Step 2: Set start node distance to zero

   The distance to the start node (0) is zero because it is the source.

3. Final Answer:

   dist = [float('inf')] * 5; dist[0] = 0 -> Option D

4. Quick Check:

   Start node distance = 0, others = infinity [OK]

Hint: Start distance zero, others infinity for shortest path [OK]

Common Mistakes:

• Setting start node distance to infinity
• Using invalid index dist[5] (out of range)
• Initializing distances with zeros

3. Given the DAG edges with weights: 0->1 (2), 0->2 (4), 1->2 (1), 1->3 (7), 2->3 (3), and start node 0, what is the shortest distance to node 3 after running shortest path using topological order?

medium

A. 6

B. 7

C. 9

D. 10

Solution

1. Step 1: Calculate distances step-by-step

   Start dist: [0, inf, inf, inf]. 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[3]=min(9,3+3=6)=6.

2. Step 2: Final shortest distance to node 3

   The shortest distance to node 3 is 6 after updates.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest path to 3 = 6 [OK]

Hint: Update distances using topological order edges [OK]

Common Mistakes:

• Not updating dist[2] to 3 via node 1
• Taking longer path 0->1->3 as shortest
• Ignoring edge weights when updating distances

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

dist = [float('inf')] * 4
dist[0] = 0
topo_order = [0, 1, 2, 3]
graph = {0: [(1, 1), (2, 4)], 1: [(2, 2), (3, 6)], 2: [(3, 3)], 3: []}
for u in topo_order:
    for v, w in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
print(dist)

What is the output?

medium

A. [0, 1, 2, 5]

B. [0, 1, 4, 7]

C. [0, 1, 3, 6]

D. [0, 1, 3, 9]

Solution

1. Step 1: Initialize distances and process node 0

   dist = [0, inf, inf, inf]. From 0: dist[1]=1, dist[2]=4.

2. Step 2: Process node 1 and update distances

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

3. Step 3: Process node 2 and update distance

   From 2: dist[3]=min(7,3+3=6)=6.

4. Step 4: Final distances array

   dist = [0, 1, 3, 6]

5. Final Answer:

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

6. Quick Check:

   Distances updated correctly using topological order [OK]

Hint: Update dist[v] only if new path is shorter [OK]

Common Mistakes:

• Not updating dist[2] to 3 via node 1
• Using wrong edge weights
• Printing dist before updates complete

5. You have a DAG with nodes 0 to 4 and edges: 0->1 (3), 0->2 (6), 1->2 (4), 1->3 (4), 2->3 (8), 3->4 (2). Using topological order [0,1,2,3,4], what is the shortest path distance from node 0 to node 4?

hard

A. 15

B. 9

C. 13

D. 11

Solution

1. Step 1: Initialize distances and update from node 0

   dist = [0, inf, inf, inf, inf]. From 0: dist[1]=3, dist[2]=6.

2. Step 2: Update distances from node 1 and 2

   From 1: dist[2]=min(6,3+4=7)=6 (unchanged), dist[3]=3+4=7. From 2: dist[3]=min(7,6+8=14)=7 (unchanged).

3. Step 3: Update distance from node 3 to 4

   dist[4]=7+2=9.

4. Step 4: Final shortest distance to node 4

   The shortest distance to node 4 is 9.

5. Final Answer:

   9 -> Option B

6. Quick Check:

   Shortest path 0->1->3->4 = 9 [OK]

Hint: Check all edges in topological order for shortest updates [OK]

Common Mistakes:

• Choosing longer path 0->2->3->4
• Adding weights incorrectly
• Ignoring topological order updates