# Shortest Paths on Directed Acyclic Graphs (DAG) ## Introduction When a directed graph is acyclic (DAG), shortest paths from a given source can be found in **linear time** by performing a topological sort and then relaxing edges in topological order. ## Approach (intuition) - Topologically sort vertices. - Initialize distances with `+∞`, distance[source] = 0. - Scan vertices in topological order; for each outgoing edge `(u→v, w)`, relax: `dist[v] = min(dist[v], dist[u] + w)`. ## Complexity - Time: **O(V + E)** (topological sort + one pass of relaxations) - Space: **O(V + E)** ## Why this is fast Topological order guarantees that when we process `u`, we have already computed the final shortest distance to `u` — no need for repeated relaxations. ## Reference implementation Full file: `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/DAG.cpp` ### Key snippet (topological recursion) ```cpp\nvoid Topological(int s, vector<pair<long long,int>> adj[], vector<int>& vis, stack<int>& res) { vis[s]= 1; for (auto &e: adj[s]) if (!vis[e.first]) Topological(e.first, adj, vis, res); res.push(s); }\n``` ``` ## Example & Usage The repo contains a sample input. The code reconstructs the path and prints both cost and path. ## Practical notes - DAG shortest paths allow negative edge weights (no cycles — so negative cycles impossible). - Validate input is a DAG first (detect cycles) when required. ## Source `https: //github.com/mashrur-rahman-fahim/algorithm/blob/main/DAG.cpp`.