Shortest Path in a Weighted Directed Acyclic Graph | Topological-Sort + Relaxation | Python

Learn how to find single source shortest path in a weighted directed acyclic graph (DAG) in linear time. We explain topological sorting by DFS, step-by-step edge relaxation, include fully-commented Python code, a hand dry-run, and clear Big-O analysis.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

Given

• V ­– number of vertices labeled 0 … V-1
• E ­– number of directed edges
• edges[i] = [u, v, w] ­– an edge from u to v with positive weight w

return an array distance where

• distance[i] = length of the shortest path from source 0 to vertex i
• If vertex i is unreachable, store -1.

Because the graph is a directed acyclic graph (DAG), there are no cycles.

2. Quick example

V = 6
edges = [
  [0,1,2], [0,4,1],
  [1,2,3], [4,2,2],
  [2,3,6], [4,5,4], [5,3,1]
]

One set of shortest distances from source 0 is

[0, 2, 3, 6, 1, 5]

• 0 → 4 → 2 → … is cheaper than 0 → 1 → 2, etc.
• Vertex 3 is reached through 0 → 4 → 5 → 3 with total weight 6.

3. Intuition & approach

3.1 Why topological sort?

In a DAG you can line up vertices so that every edge goes left-to-right.
If you relax (update) edges in that order, by the time you process a vertex, its current distance is already the final shortest distance, no need for revisiting like Dijkstra or Bellman-Ford.

3.2 Algorithm steps

1. Build an adjacency list u → (v, w).
2. Topological sort all vertices with a DFS:
   • Start DFS from every unvisited node.
   • After finishing a node, push it onto a stack.
   • When DFS ends, popping the stack yields a valid topo order.
3. Single-source relaxation in topo order:
   • Set distance[src] = 0, all others to ∞.
   • Pop vertices one by one.
   • For each outgoing edge u → v with weight w,
     • if distance[u] + w < distance[v], update distance[v].
4. Post-process – convert every ∞ to -1 for unreachable nodes.

Because edges only go forward in the order, each one is relaxed exactly once, giving an O(V + E) time algorithm, the best you can hope for in a DAG.

4. Python code

from typing import List

class Solution:
    # ---------- DFS for topological sort ----------
    def dfs(self, node, stack, visited, adj_list):
        visited[node] = 1
        for adjNode, _ in adj_list[node]:         # ignore weight during DFS
            if visited[adjNode] == 0:
                self.dfs(adjNode, stack, visited, adj_list)
        stack.append(node)                        # post-order push

    # ---------- main function ----------
    def shortestPath(self, V: int, E: int, edges: List[List[int]]) -> List[int]:
        # 1. Build adjacency list
        adj_list = [[] for _ in range(V)]
        for u, v, w in edges:                     # directed edge u -> v (weight w)
            adj_list[u].append([v, w])

        # 2. Topological sort by DFS
        stack   = []
        visited = [0] * V
        for i in range(V):
            if visited[i] == 0:
                self.dfs(i, stack, visited, adj_list)

        # 3. Initialise distance array
        distance = [float("inf")] * V
        distance[0] = 0                           # source vertex

        # 4. Relax edges following topological order
        while stack:                              # pop = left-to-right order
            node = stack.pop()
            if distance[node] == float("inf"):    # unreachable so far
                continue
            for adjNode, w in adj_list[node]:
                new_d = distance[node] + w
                if new_d < distance[adjNode]:
                    distance[adjNode] = new_d

        # 5. Replace infinity by -1 as problem demands
        for i in range(V):
            if distance[i] == float("inf"):
                distance[i] = -1
        return distance

5. Detailed step-by-step explanation

1. Adjacency list – quickly lists (neighbour, weight) pairs for every vertex.
2. dfs routine – a classic post-order push guarantees parents appear after children in the stack, which reverses to topo order when popped.
3. Distance array – ∞ (here float('inf')) means “not reached yet”.
4. Relaxation loop
   • If the current node is still at ∞, no shorter path can arise later because no incoming edges remain, so we skip it.
   • Otherwise explore its outgoing edges and update neighbours if we find a cheaper route.
5. Final loop converts unreached vertices to -1 per the spec.

Because each vertex and edge is touched only once across DFS + relaxation, the algorithm is linear.

6. Dry run on the sample graph

Relaxation in that pop order produces the distances 0 2 3 6 1 5.

7. Complexity analysis

8.Conclusion

When the graph is a weighted DAG, the combination of topological sorting plus single-pass edge relaxation gives the fastest and simplest single-source shortest-path algorithm:

• Linear time – beats Dijkstra (needs a heap) and Bellman-Ford (multi-pass).
• In-place friendly – only a handful of arrays, no exotic data structures.
• Conceptually clear – once you trust topological order, relaxation is guaranteed to be final.

Next time you see a DAG with weights, reach straight for this technique!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.