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

Shortest Path in DAG Using Topological Order

📖 Scenario: You are working on a project to find the shortest path 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 where some tasks must be done before others.

🎯 Goal: Build a Python program that finds the shortest distance from a given start node to all other nodes in a DAG using topological sorting.

📋 What You'll Learn

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

Create a list to store the topological order of nodes

Implement a function to perform topological sort using DFS

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

Print the shortest distances in the required format

💡 Why This Matters

🌍 Real World

Finding shortest paths in DAGs is useful in project scheduling, task ordering, and optimizing workflows where some tasks depend on others.

💼 Career

Understanding shortest path algorithms in DAGs is important for software engineers working on compilers, build systems, and data processing pipelines.

1

Create the DAG as an adjacency list

Create a dictionary called graph representing the DAG with these exact edges and weights: 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). Use the format graph = {0: [(1, 5), (2, 3)], ...}.

DSA Python

# Your code here

Hint

Use a dictionary where keys are node numbers and values are lists of tuples (neighbor, weight).

2

Create a list to store topological order and a visited set

Create an empty list called topo_order to store the topological order of nodes and an empty set called visited to keep track of visited nodes.

DSA Python

graph = {
    0: [(1, 5), (2, 3)],
    1: [(3, 6), (2, 2)],
    2: [(4, 4), (5, 2), (3, 7)],
    3: [(4, -1)],
    4: [(5, -2)],
    5: []
}
# Your code here

Hint

Use topo_order = [] and visited = set() to prepare for DFS.

3

Implement DFS for topological sort and find shortest paths

Define a function called dfs(node) that marks node as visited, recursively visits all neighbors in graph[node], and appends node to topo_order. Then, create a list dist with length 6, initialized with float('inf'). Set dist[0] = 0 as the start node distance. Run DFS for all nodes from 0 to 5 if not visited. Reverse topo_order. Finally, for each node in topo_order, update distances of neighbors if a shorter path is found.

DSA Python

graph = {
    0: [(1, 5), (2, 3)],
    1: [(3, 6), (2, 2)],
    2: [(4, 4), (5, 2), (3, 7)],
    3: [(4, -1)],
    4: [(5, -2)],
    5: []
}
topo_order = []
visited = set()
# Your code here

Hint

Use DFS to fill topo_order. Then update dist using the topological order.

4

Print the shortest distances from start node

Print the list dist exactly as it is to show shortest distances from node 0 to all other nodes.

DSA Python

graph = {
    0: [(1, 5), (2, 3)],
    1: [(3, 6), (2, 2)],
    2: [(4, 4), (5, 2), (3, 7)],
    3: [(4, -1)],
    4: [(5, -2)],
    5: []
}
topo_order = []
visited = set()

def dfs(node):
    visited.add(node)
    for neighbor, _ in graph[node]:
        if neighbor not in visited:
            dfs(neighbor)
    topo_order.append(node)

dist = [float('inf')] * 6
start = 0

dist[start] = 0

for node in range(6):
    if node not in visited:
        dfs(node)

topo_order.reverse()

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

# Print the shortest distances
# Your code here

Hint

Use print(dist) to show the 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 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