GraphProblem 30 of 43
Longest path in a Directed Acyclic Graph
Problem Statement
Given a weighted Directed Acyclic Graph (DAG) and a source vertex, find the longest path from the source to all other vertices.
Example:
- Input:
V = 6, source = 1, edges = [(0,1,5), (0,2,3), (1,3,6), (1,2,2), (2,4,4), (2,5,2), (2,3,7), (3,5,1), (3,4,-1), (4,5,-2)] - Output:
Longest distances from source 1: [INF, 0, 2, 9, 8, 10]
Noob-Friendly Explanation
Imagine you're playing a video game where each level is connected by paths with points. You want to collect the MAXIMUM points while travelling from your starting level to the final level. You can only move forward (no going back — that's the "acyclic" part).
For shortest path, we minimize. For longest path, we can negate all weights and find the shortest path, OR we can use topological sort and relax edges in the opposite direction (maximize instead of minimize).
Approach 1: Brute Force (DFS all paths)
Intuition
Explore all possible paths from source to each destination using DFS. Track the maximum distance found for each vertex.
Algorithm
- For each vertex, try all paths from source to that vertex using DFS.
- For each path, sum up the edge weights.
- Keep the maximum distance found for each vertex.
java
import java.util.*;
public class LongestPathBrute {
static int[] maxDist;
static Map<Integer, List<int[]>> adj;
public static void longestPath(int V, int src, int[][] edges) {
adj = new HashMap<>();
for (int i = 0; i < V; i++) adj.put(i, new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(new int[]{e[1], e[2]});
}
maxDist = new int[V];
Arrays.fill(maxDist, Integer.MIN_VALUE);
maxDist[src] = 0;
boolean[] visited = new boolean[V];
dfs(src, 0, visited);
System.out.println("Longest distances from source " + src + ":");
for (int i = 0; i < V; i++) {
if (maxDist[i] == Integer.MIN_VALUE) {
System.out.print("INF ");
} else {
System.out.print(maxDist[i] + " ");
}
}
System.out.println();
}
static void dfs(int u, int distSoFar, boolean[] visited) {
visited[u] = true;
maxDist[u] = Math.max(maxDist[u], distSoFar);
for (int[] edge : adj.get(u)) {
int v = edge[0], w = edge[1];
if (!visited[v]) {
dfs(v, distSoFar + w, visited);
}
}
visited[u] = false; // backtrack to allow other paths
}
public static void main(String[] args) {
int V = 6;
int[][] edges = {
{0,1,5},{0,2,3},{1,3,6},{1,2,2},
{2,4,4},{2,5,2},{2,3,7},{3,5,1},
{3,4,-1},{4,5,-2}
};
longestPath(V, 1, edges);
}
}Complexity Analysis
- Time Complexity: O(V! * E) - in worst case, DFS explores an exponential number of paths
- Space Complexity: O(V) - for visited array and recursion stack
Approach 2: Optimal (Topological Sort + DP)
Intuition
In a DAG, topological sort gives us an ordering where every edge goes from earlier to later. Process vertices in topological order and for each vertex, update distances to its neighbours (maximize instead of minimize).
Algorithm
- Compute topological sort of the DAG.
- Initialize distances:
dist[source] = 0, all others = -infinity. - Process vertices in topological order. For each vertex u with a valid distance, update
dist[v] = max(dist[v], dist[u] + weight(u,v))for all neighbours v.
java
import java.util.*;
public class LongestPathDAG {
public static void longestPath(int V, int src, List<List<int[]>> adj) {
// Step 1: Topological Sort using DFS
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) {
topoSort(i, adj, visited, stack);
}
}
// Step 2: Initialize distances
int[] dist = new int[V];
Arrays.fill(dist, Integer.MIN_VALUE);
dist[src] = 0;
// Step 3: Process in topological order
while (!stack.isEmpty()) {
int u = stack.pop();
if (dist[u] == Integer.MIN_VALUE) continue;
for (int[] edge : adj.get(u)) {
int v = edge[0], w = edge[1];
if (dist[u] + w > dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// Print results
System.out.println("Longest distances from source " + src + ":");
for (int i = 0; i < V; i++) {
if (dist[i] == Integer.MIN_VALUE) {
System.out.print("INF ");
} else {
System.out.print(dist[i] + " ");
}
}
System.out.println();
}
static void topoSort(int u, List<List<int[]>> adj, boolean[] visited, Stack<Integer> stack) {
visited[u] = true;
for (int[] edge : adj.get(u)) {
if (!visited[edge[0]]) {
topoSort(edge[0], adj, visited, stack);
}
}
stack.push(u);
}
public static void main(String[] args) {
int V = 6;
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
adj.get(0).add(new int[]{1, 5});
adj.get(0).add(new int[]{2, 3});
adj.get(1).add(new int[]{3, 6});
adj.get(1).add(new int[]{2, 2});
adj.get(2).add(new int[]{4, 4});
adj.get(2).add(new int[]{5, 2});
adj.get(2).add(new int[]{3, 7});
adj.get(3).add(new int[]{5, 1});
adj.get(3).add(new int[]{4, -1});
adj.get(4).add(new int[]{5, -2});
longestPath(V, 1, adj);
}
}Complexity Analysis
- Time Complexity: O(V + E) - topological sort is O(V + E), then processing each edge once
- Space Complexity: O(V + E) - for adjacency list, stack, visited, and distance arrays