G-27. Shortest Path in Directed Acyclic Graph - Topological Sort

1. Problem Statement & Context

When analyzing graphs, finding the shortest path from a single source node to all other vertices is a classic foundational problem.

• Graph Type: Directed Acyclic Graph (DAG) — a directed graph containing no cycles.
• Edge Weights: Unlike unweighted graphs where edges have a uniform cost of 1, edges in this problem carry weights (e.g., traveling from node 0 to 1 costs 2).
• Objective: Find the shortest distance from a designated source node (conventionally node 0, though the algorithm handles any source) to every other vertex in the graph (0 through N-1).

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy (Task Dependency Workflow): Imagine managing a complex software release project where certain tasks must be completed before others can begin (dependencies). If you process tasks in a random order, you might try to compute the cost of a downstream task before its prerequisites are fully evaluated.

By arranging tasks using Topological Sort, you guarantee that you never evaluate a node until all incoming paths (prerequisites) have already been fully calculated and finalized.

3. Naive vs. Optimal Approach

4. Graph Representation with Edge Weights

To store weighted graphs in memory, we modify our adjacency list from storing simple integers to storing pairs of (adjacent_node, weight).

5. Step-by-Step Algorithm Breakdown

The solution is divided into two distinct, sequential steps:

1. Step 1: Topological Sort: Run a Depth-First Search (DFS) across all graph components to generate a linear ordering of nodes stored in a stack.
2. Step 2: Edge Relaxation: Pop nodes off the stack one by one. For each node, inspect its adjacent neighbors and "relax" the edge weights to discover the shortest path.

6. Complete Flow Walkthrough (Trace Example)

Assume a graph with nodes 0 through 6 and source node 6.

Step 1: Topological Sort (DFS Stack Result)

Step 2: Distance Array Initialization & Edge Relaxation

• Initial State: All distances set to infinity (1e9), except distance[source] = 0.
• Iteration 1: Pop 6 (Stack Top).
  • Distance to 6 is 0.
  • Neighbors: 5 (weight 3) and 4 (weight 2).
  • Update: distance[5] = 3, distance[4] = 2.
• Iteration 2: Pop 5.
  • Distance to 5 is 3.
  • Neighbor: 4 (weight 1). Potential distance: 3 + 1 = 4. Since current distance[4] is 2 (which is shorter), we omit the update.
• Iteration 3: Pop 4.
  • Distance to 4 is 2.
  • Neighbors: 0 (weight 3) and 2 (weight 1).
  • Update: distance[0] = 2 + 3 = 5, distance[2] = 2 + 1 = 3.

(This process continues down the stack until all nodes have been popped and their outgoing edges relaxed.)

7. Implementation Code

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    void topoSort(int node, vector<pair<int, int>> adj[], vector<int>& vis, stack<int>& st) {
        vis[node] = 1;
        for (auto it : adj[node]) {
            int v = it.first;
            if (!vis[v]) {
                topoSort(v, adj, vis, st);
            }
        }
        st.push(node);
    }

public:
    vector<int> shortestPath(int N, int M, vector<vector<int>>& edges) {
        // Step 1: Create adjacency list with pairs (neighbor, weight)
        vector<pair<int, int>> adj[N];
        for (int i = 0; i < M; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            int wt = edges[i][2];
            adj[u].push_back({v, wt});
        }

        // Step 2: Find topological sort using DFS
        vector<int> vis(N, 0);
        stack<int> st;
        for (int i = 0; i < N; i++) {
            if (!vis[i]) {
                topoSort(i, adj, vis, st);
            }
        }

        // Step 3: Initialize distance array with infinity (1e9)
        vector<int> dist(N, 1e9);
        
        // Assuming source is 0 (or adjust based on problem prompt)
        int src = 0; 
        dist[src] = 0;

        // Step 4: Process nodes from stack and relax edges
        while (!st.empty()) {
            int node = st.top();
            st.pop();

            if (dist[node] != 1e9) {
                for (auto it : adj[node]) {
                    int v = it.first;
                    int wt = it.second;

                    if (dist[node] + wt < dist[v]) {
                        dist[v] = dist[node] + wt;
                    }
                }
            }
        }

        // Optional: Replace unreachable 1e9 markers with -1 if required
        for (int i = 0; i < N; i++) {
            if (dist[i] == 1e9) {
                dist[i] = -1; // Or keep 1e9 as per online judge specification
            }
        }

        return dist;
    }
};

8. Real-World Practical Pitfalls & Debugging Mindset

• Unreachable Nodes: If a node cannot be reached from the source, its distance remains infinity (1e9). Ensure your output expectations match the platform requirements (some judges expect 1e9 or 1e18, while others expect -1).
• Graph Cycles: If the graph contains a cycle, a Topological Sort is impossible. Always verify that the input graph is strictly a Directed Acyclic Graph (DAG) before applying this algorithm.
• Source Selection: Hardcoding the source node as 0 is common, but ensure your implementation easily accommodates an arbitrary source node if specified by an interviewer.

9. Summary and Key Takeaways

• Problem Domain: Finding shortest paths in a Directed Acyclic Graph (DAG) with edge weights.
• Algorithm Composition: Combines Topological Sort (DFS) with Edge Relaxation.
• Efficiency: Runs in $O(V + E)$ time complexity, outperforming general shortest path algorithms like Dijkstra on DAG structures.
• Prerequisite Safety: Topological ordering guarantees that every node is processed strictly after all its incoming dependencies have been fully evaluated.
• Data Structure Choice: Adjacency lists must store pairs containing both the adjacent node and the edge weight.
• Linear Propagation: Distance updates flow naturally from the source outward, eliminating the need for priority queues or iterative graph re-visitations.