Shortest Path in a Directed Acyclic Graph (DAG)

63.6k
0

Given a weighted directed acyclic graph with V vertices numbered from 0 to V - 1 and E directed weighted edges, find the shortest distance from source vertex 0 to every vertex.

Each edge is represented as [u, v, wt], meaning a directed edge from u to v with weight wt. Return -1 for every vertex unreachable from source.

Example 1

Input: V = 4, E = 2, edges = [[0,1,2],[0,2,1]]

Output: [0,2,1,-1]

Explanation: Vertices 1 and 2 are directly reachable from source. Vertex 3 is unreachable, so distance is -1.

Example 2

Input: V = 6, E = 7, edges = [[0,1,2],[0,4,1],[4,5,4],[4,2,2],[1,2,3],[2,3,6],[5,3,1]]

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

Explanation: Shortest routes are 0->1, 0->4->2, 0->4->5->3, 0->4, and 0->4->5.

DFS Approach

A directed acyclic graph has a topological ordering where every edge moves from an earlier vertex to a later vertex. Processing vertices in such order ensures that all possible incoming paths have contributed before outgoing edges are relaxed.

DFS creates the topological order by adding each vertex after all outgoing paths finish. Distances then propagate from source 0, with every directed edge relaxed exactly once.

Algorithm

  • Build a weighted adjacency list from the edge list, storing every destination vertex with the corresponding edge weight.

  • Run DFS from every unvisited vertex and push each vertex onto a stack after processing all outgoing neighbors, producing topological order in reverse finishing time.

  • Initialize every distance as infinity and set distance[0] to 0, establishing vertex 0 as the source.

  • Remove vertices from the topological stack one by one, ensuring that every predecessor is processed before the corresponding dependent vertex.

  • Skip relaxation when the current distance remains infinity, as no path from the source reaches the current vertex.

  • For every outgoing edge (current, neighbor, weight), update distance[neighbor] with the smaller of the existing value and distance[current]+weight.

  • Replace all remaining infinity values with -1 and return the distance array, marking every unreachable vertex explicitly.

Dry Run

shortest-path-dag-dfs-detailed-dry-run

shortest-path-dag-dfs-detailed-dry-run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Store nodes after exploring outgoing edges.
void dfs(int node, vector<vector<pair<int, int>>>& adj,
vector<int>& visited, stack<int>& topo) {
// Mark current node visited.
visited[node] = 1;
// Visit every outgoing neighbor.
for (auto& edge : adj[node]) {
int nextNode = edge.first;
if (!visited[nextNode]) {
dfs(nextNode, adj, visited, topo);
}
}
// Push after descendants to create topological order.
topo.push(node);
}
public:
// Return shortest distances from source 0 in a weighted DAG.
vector<int> shortestPath(int V, int E, vector<vector<int>>& edges) {
vector<vector<pair<int, int>>> adj(V);
// Build directed weighted adjacency list.
for (vector<int>& edge : edges) {
int from = edge[0];
int to = edge[1];
int weight = edge[2];
adj[from].push_back({to, weight});
}
vector<int> visited(V, 0);
stack<int> topo;
// Run DFS from every component to cover all vertices.
for (int node = 0; node < V; node++) {
if (!visited[node]) {
dfs(node, adj, visited, topo);
}
}
const int INF = 1e9;
vector<int> dist(V, INF);
// Source vertex is fixed as 0.
dist[0] = 0;
// Relax edges following topological order.
while (!topo.empty()) {
int node = topo.top();
topo.pop();
// Skip vertices unreachable from source.
if (dist[node] == INF) {
continue;
}
// Improve distances of outgoing neighbors.
for (auto& edge : adj[node]) {
int nextNode = edge.first;
int weight = edge.second;
if (dist[node] + weight < dist[nextNode]) {
dist[nextNode] = dist[node] + weight;
}
}
}
// Convert unreachable vertices from INF to -1.
for (int node = 0; node < V; node++) {
if (dist[node] == INF) {
dist[node] = -1;
}
}
return dist;
}
};
// Driver code.
int main() {
int V = 6;
int E = 7;
vector<vector<int>> edges = {
{0, 1, 2}, {0, 4, 1}, {4, 5, 4}, {4, 2, 2},
{1, 2, 3}, {2, 3, 6}, {5, 3, 1}
};
Solution sol;
vector<int> ans = sol.shortestPath(V, E, edges);
// Print shortest distances.
for (int value : ans) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(V+E), where V and E are the numbers of vertices and directed edges; topological DFS and relaxation process each vertex and edge once.

Space Complexity: O(V+E), where the adjacency list stores V vertices and E edges, while the visited, stack, recursion, and distance storage require O(V) space.

BFS Approach

In a directed acyclic graph, every edge goes from an earlier vertex to a later vertex in some topological ordering. That ordering is the key reason shortest paths can be found without repeatedly revisiting vertices.

Kahn's algorithm creates this ordering using indegree counts. Vertices with no remaining incoming dependency are processed first, and removing them gradually exposes the next safe vertices.

After the order is ready, the distance of each vertex is finalized enough to pass its value forward. Every outgoing edge can then improve the neighbor's distance. Since edges only move forward in the ordering, a later vertex never needs to affect an earlier one.

Algorithm

  • Build an adjacency list from the edge list, and store each outgoing neighbor with its edge weight.

  • Compute the indegree of every vertex, then place all zero-indegree vertices into a queue.

  • Repeatedly remove a vertex from the queue, append it to the topological order, reduce the indegree of its outgoing neighbors, and enqueue any neighbor whose indegree becomes zero.

  • Initialize all distances as unreachable, then set the distance of source vertex 0 to 0; if no other vertex can be reached, these unreachable markers remain unchanged.

  • Traverse the topological order and skip vertices that are still unreachable; for every reachable vertex, relax all outgoing edges.

  • Convert every remaining unreachable distance to -1 and return the final distance array.

Dry Run

shortest-path-dag-kahn-bfs-verified

shortest-path-dag-kahn-bfs-verified

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns shortest distances from source vertex 0.
vector<int> shortestPath(int V, int E, vector<vector<int>>& edges) {
vector<vector<pair<int, int>>> adjacency(V);
vector<int> indegree(V, 0);
// Build adjacency list and indegree values from the directed edges.
for (int i = 0; i < E; i++) {
int u = edges[i][0];
int v = edges[i][1];
int weight = edges[i][2];
adjacency[u].push_back({v, weight});
indegree[v]++;
}
queue<int> nodes;
// Add every vertex that has no incoming edge.
for (int node = 0; node < V; node++) {
// Zero-indegree vertices can start the topological ordering.
if (indegree[node] == 0) {
nodes.push(node);
}
}
vector<int> topo;
// Remove vertices in BFS order while their outgoing edges reduce indegrees.
while (!nodes.empty()) {
int node = nodes.front();
nodes.pop();
topo.push_back(node);
for (auto edge : adjacency[node]) {
int nextNode = edge.first;
indegree[nextNode]--;
// A neighbor becomes ready when all incoming dependencies are removed.
if (indegree[nextNode] == 0) {
nodes.push(nextNode);
}
}
}
const long long INF = 1000000000000000000LL;
vector<long long> dist(V, INF);
dist[0] = 0;
// Relax edges only after the source distance to a vertex is known.
for (int node : topo) {
// Unreachable vertices cannot improve any neighbor.
if (dist[node] == INF) {
continue;
}
for (auto edge : adjacency[node]) {
int nextNode = edge.first;
int weight = edge.second;
// A shorter path through the current vertex replaces the old distance.
if (dist[node] + weight < dist[nextNode]) {
dist[nextNode] = dist[node] + weight;
}
}
}
vector<int> answer(V, -1);
for (int node = 0; node < V; node++) {
// Reachable vertices keep their computed shortest distance.
if (dist[node] != INF) {
answer[node] = dist[node];
}
}
return answer;
}
};
// Driver code
int main() {
int V = 6;
int E = 7;
vector<vector<int>> edges = {
{0, 1, 2},
{0, 4, 1},
{1, 2, 3},
{4, 2, 2},
{4, 5, 4},
{2, 3, 6},
{5, 3, 1}
};
// instance for class Solution
Solution sol;
vector<int> answer = sol.shortestPath(V, E, edges);
for (int value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(V + E), because Kahn's algorithm processes every vertex and edge once, and the relaxation phase also scans every directed edge once.

Space Complexity: O(V + E), because the adjacency list stores all edges, and the indegree, queue, topological order, and distance arrays store vertex-level data.

Interview follow-up Questions

Topological order processes every vertex after all possible earlier contributors, so one relaxation pass is enough.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: DisjointSet(int...

91k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.3k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return the minimum time...

81.3k
Comments0