Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Shortest Path in a Weighted Directed Acyclic Graph | Topological-Sort + Relaxation | Python
    Data Structures & Algorithms

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

    codeanddebugBy codeanddebug17 June 2025Updated:17 June 2025No Comments5 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of question to Find the Shortest Path in a Directed Graph
    Share
    Facebook Twitter LinkedIn Pinterest Email

    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.

    Contents:
     [show]
    • 1. What does the problem ask?
    • 2. Quick example
    • 3. Intuition & approach
      • 3.1 Why topological sort?
      • 3.2 Algorithm steps
    • 4. Python code
    • 5. Detailed step-by-step explanation
    • 6. Dry run on the sample graph
    • 7. Complexity analysis
    • 8.Conclusion

    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

    Stack build (push order)Stack after DFSPop order (topo)
    5, 4, 2, 1, 3, 0 (example)[5,4,2,1,3,0]0 → 3 → 1 → 2 → 4 → 5

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


    7. Complexity analysis

    MetricCostWhy
    TimeO(V + E)DFS visits each vertex/edge once; relaxation does the same
    SpaceO(V + E)Adjacency list + call stack + distance + visited arrays

    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!

    Join our Advance DSA COURSE

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

    DFS Graph Shortest Path
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleShortest Path in an Undirected Graph with Unit Distance – Clear BFS Solution in Python
    Next Article Dijkstra’s Algorithm with a Priority Queue
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    7 July 2025
    Data Structures & Algorithms

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025
    Data Structures & Algorithms

    Missing And Repeating – GeeksforGeeks Solution Explained

    7 July 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (99)
      • Beginner (44)
      • Expert (28)
      • Intermediate (27)
    • Uncategorised (1)
    Recent Posts

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    7 July 2025

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025

    Missing And Repeating – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Without Extra Space – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Intervals | Leetcode 56 | Brute Force and Optimal

    7 July 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.