Shortest Path in DAG Using Topological Order in DSA Python

Mental Model

We find the shortest path in a graph with no cycles by first arranging nodes in order so all edges go forward, then updating shortest distances step by step.

Analogy: Imagine tasks that must be done in order, like cooking steps. You list them so each step comes after its prerequisites, then find the quickest way to finish all tasks by checking each step once in order.

Graph nodes arranged in order:
1 -> 2 -> 3 -> 4 -> null
Edges only go forward, no loops.

Dry Run Walkthrough

Input: Graph edges with weights: 1->2(3), 1->3(6), 2->3(4), 2->4(4), 3->4(8), start node = 1

Goal: Find shortest distances from node 1 to all others using topological order

Step 1: Find topological order: [1, 2, 3, 4]

Order: 1 -> 2 -> 3 -> 4 -> null

Why: We need to process nodes so all edges go forward to update distances correctly

Step 2: Initialize distances: dist[1]=0, others=∞

distances: [1:0, 2:∞, 3:∞, 4:∞]

Why: Start node distance is zero, others unknown

Step 3: Process node 1: update dist[2]=3, dist[3]=6

distances: [1:0, 2:3, 3:6, 4:∞]

Why: From node 1, edges to 2 and 3 update their shortest distances

Step 4: Process node 2: update dist[3]=min(6,3+4=7)=6, dist[4]=3+4=7

distances: [1:0, 2:3, 3:6, 4:7]

Why: From node 2, check if paths improve distances to 3 and 4

Step 5: Process node 3: update dist[4]=min(7,6+8=14)=7

distances: [1:0, 2:3, 3:6, 4:7]

Why: From node 3, check if path improves distance to 4

Step 6: Process node 4: no outgoing edges, distances unchanged

distances: [1:0, 2:3, 3:6, 4:7]

Why: No further updates possible

Result:

Final shortest distances: 1:0 -> 2:3 -> 3:6 -> 4:7

Annotated Code

DSA Python

from collections import defaultdict, deque

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))

    def topological_sort(self):
        in_degree = [0] * (self.V + 1)
        for u in self.graph:
            for v, _ in self.graph[u]:
                in_degree[v] += 1

        queue = deque()
        for i in range(1, self.V + 1):
            if in_degree[i] == 0:
                queue.append(i)

        topo_order = []
        while queue:
            u = queue.popleft()
            topo_order.append(u)
            for v, _ in self.graph[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    queue.append(v)
        return topo_order

    def shortest_path(self, start):
        dist = [float('inf')] * (self.V + 1)
        dist[start] = 0

        topo_order = self.topological_sort()

        for u in topo_order:
            if dist[u] != float('inf'):
                for v, w in self.graph[u]:
                    if dist[v] > dist[u] + w:
                        dist[v] = dist[u] + w
        return dist

if __name__ == '__main__':
    g = Graph(4)
    g.add_edge(1, 2, 3)
    g.add_edge(1, 3, 6)
    g.add_edge(2, 3, 4)
    g.add_edge(2, 4, 4)
    g.add_edge(3, 4, 8)

    distances = g.shortest_path(1)
    for i in range(1, 5):
        if distances[i] == float('inf'):
            print(f'{i}: unreachable')
        else:
            print(f'{i}: {distances[i]}')

for i in range(1, self.V + 1): if in_degree[i] == 0: queue.append(i)

Initialize queue with nodes having zero incoming edges for topological order

while queue: u = queue.popleft() topo_order.append(u) for v, _ in self.graph[u]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v)

Build topological order by removing edges and adding nodes with zero in-degree

dist = [float('inf')] * (self.V + 1) dist[start] = 0

Initialize distances with infinity except start node zero

for u in topo_order: if dist[u] != float('inf'): for v, w in self.graph[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w

Relax edges in topological order to update shortest distances

Output

1: 0

2: 3

3: 6

4: 7

Complexity Analysis

Time: O(V + E) because we do a topological sort and then relax each edge once

Space: O(V + E) for storing graph and distance arrays

vs Alternative: Compared to Dijkstra's algorithm, this is faster for DAGs because no priority queue is needed and edges are relaxed once in order

Edge Cases

Graph with no edges

Distances remain infinity except start node zero

DSA Python

dist[start] = 0

Graph with unreachable nodes

Unreachable nodes keep distance infinity and print 'unreachable'

DSA Python

if distances[i] == float('inf'):
            print(f'{i}: unreachable')

Single node graph

Distance to start node is zero, no other nodes

DSA Python

dist[start] = 0

When to Use This Pattern

When you see a graph with no cycles and need shortest paths, use topological order to process nodes once and update distances efficiently.

Common Mistakes

Mistake: Not computing topological order before relaxing edges
Fix: Always perform topological sort first to ensure edges go forward and distances update correctly

Mistake: Initializing distances incorrectly or forgetting to set start node distance to zero
Fix: Set start node distance to zero explicitly before relaxing edges

Summary

Finds shortest paths in a graph without cycles by processing nodes in order.

Use when the graph is a Directed Acyclic Graph (DAG) and you want efficient shortest paths.

The key is to process nodes in topological order so all edges go forward and distances update once.

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