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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of shortest path distances in a DAG

What is the output of the shortest path distances array after running the given code on the DAG?

DSA Python

def shortest_path_dag(graph, start):
    from collections import deque
    n = len(graph)
    indegree = [0]*n
    for u in range(n):
        for v, w in graph[u]:
            indegree[v] += 1
    queue = deque([start])
    dist = [float('inf')] * n
    dist[start] = 0
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return dist

graph = [
    [(1, 2), (2, 4)],
    [(2, 1), (3, 5)],
    [(4, 3)],
    [(5, 1)],
    [(3, 2), (5, 5)],
    []
]
print(shortest_path_dag(graph, 0))

A [0, 2, 3, 7, 6, 8]

B [0, 2, 4, 9, 7, 8]

C [0, 2, 3, 9, 6, 7]

D [0, 2, 3, 7, 6, 7]

💡 Hint

Trace the graph edges and update distances step-by-step using topological order.

The code uses a queue to process nodes in topological order by indegree zero. Distances are updated when a shorter path is found. The final distances from node 0 to others are [0, 2, 3, 7, 6, 8].

🧠 Conceptual

intermediate

Understanding topological order in shortest path calculation

Why is topological order important when finding the shortest path in a Directed Acyclic Graph (DAG)?

A It allows processing nodes in reverse order to find longest paths.

B It guarantees the graph has no cycles, so shortest paths are always zero.

C It sorts nodes by their distance values from the start node.

D It ensures nodes are processed only after all their predecessors, allowing correct distance updates.

💡 Hint

Think about dependencies between nodes and when distances can be finalized.

Topological order processes nodes only after all nodes leading into them are processed, ensuring all shortest distances to predecessors are known before updating the current node.

🔧 Debug

advanced

Identify the error in shortest path code for DAG

What error will the following code produce when run on a DAG with multiple disconnected components?

DSA Python

def shortest_path_dag(graph, start):
    from collections import deque
    n = len(graph)
    indegree = [0]*n
    for u in range(n):
        for v, w in graph[u]:
            indegree[v] += 1
    queue = deque([start])
    dist = [float('inf')] * n
    dist[start] = 0
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return dist

# graph with disconnected node 6
graph = [
    [(1, 2), (2, 4)],
    [(2, 1), (3, 7)],
    [(4, 3)],
    [(5, 1)],
    [(3, 2), (5, 5)],
    [],
    []
]
print(shortest_path_dag(graph, 0))

A KeyError due to accessing graph[6] which is empty

B IndexError because node 6 is not processed and queue becomes empty prematurely

C No error, but distances for disconnected node 6 remain infinity

D TypeError because indegree list is shorter than graph nodes

💡 Hint

Consider what happens to nodes not reachable from the start node.

The code does not process disconnected nodes, so their distances remain infinity. No error occurs because graph[6] is an empty list and indegree list matches graph size.

❓ Predict Output

advanced

Output of shortest path distances with negative edge weights in DAG

What is the output of the shortest path distances array after running the code on the DAG with negative edge weights?

DSA Python

def shortest_path_dag(graph, start):
    from collections import deque
    n = len(graph)
    indegree = [0]*n
    for u in range(n):
        for v, w in graph[u]:
            indegree[v] += 1
    queue = deque([start])
    dist = [float('inf')] * n
    dist[start] = 0
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return dist

graph = [
    [(1, 3), (2, 6)],
    [(2, -2), (3, 1)],
    [(3, 1)],
    []
]
print(shortest_path_dag(graph, 0))

A [0, 3, 1, 2]

B [0, 3, 1, 3]

C [0, 3, 6, 7]

D [0, 3, 4, 5]

💡 Hint

Negative edges are allowed in DAG shortest path if no cycles exist.

The shortest path distances are updated correctly even with negative edges because the graph is acyclic. Distances are: 0 to 0 is 0, to 1 is 3, to 2 is 1 (3 + -2), to 3 is 2 (1 + 1).

🚀 Application

expert

Number of nodes reachable from start in shortest path DAG algorithm

After running the shortest path algorithm on the given DAG, how many nodes have a finite shortest path distance from the start node 0?

DSA Python

def shortest_path_dag(graph, start):
    from collections import deque
    n = len(graph)
    indegree = [0]*n
    for u in range(n):
        for v, w in graph[u]:
            indegree[v] += 1
    queue = deque([start])
    dist = [float('inf')] * n
    dist[start] = 0
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return dist

graph = [
    [(1, 5)],
    [(2, 3)],
    [(3, 1)],
    [(4, 2)],
    [],
    [(6, 1)],
    []
]
distances = shortest_path_dag(graph, 0)
count = sum(1 for d in distances if d != float('inf'))
print(count)

A 4

B 5

C 6

D 7

💡 Hint

Count nodes reachable by following edges from start node 0.

Nodes 0,1,2,3,4 are reachable with finite distances. Nodes 5 and 6 are disconnected from 0, so their distances remain infinity.

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