Finding the longest path in a graph can be difficult because a general graph may contain cycles. However, if the graph is a Directed Acyclic Graph (DAG), we can solve the problem efficiently using Topological Sorting + Dynamic Programming.
1. Problem Understanding
We are given:
V vertices numbered from 0 to V - 1
A directed weighted graph
edges[i] = [u, v, w]
An edge from u to v with weight w
A source vertex src
We need to return:
dist[i] = longest distance from src to vertex i
If vertex i cannot be reached from src, we return:
Integer.MIN_VALUE
The driver code displays this as INF.
2. Example
Consider:
V = 4
src = 0
edges = [
[0, 1, 1],
[0, 2, 1],
[1, 2, 5],
[3, 1, 2],
[3, 2, -1]
]
The graph looks like:
1
0 ------> 1
| |
1| |5
↓ ↓
2 <-------
3 ------> 1
Possible paths from 0:
0 → 1
Distance:
1
Another path:
0 → 2
Distance:
1
And:
0 → 1 → 2
Distance:
1 + 5 = 6
Therefore:
[0, 1, 6, INF]
3. Main Idea
The solution has three major steps:
1. Build adjacency list
2. Find topological ordering
3. Calculate longest distances using DP
The important observation is that the graph is a DAG.
Because there are no cycles, we can process vertices in topological order.
4. Why Topological Sorting?
A topological ordering places every vertex before all vertices that it points to.
For example:
0 → 1 → 2
A valid topological order is:
0, 1, 2
When we process 1, we already know the best distance to 1.
Therefore, when we process 2, we can safely calculate:
dist[2] = dist[1] + weight
This makes the problem similar to Dynamic Programming.
5. Complete Java Code
import java.util.*;
class Solution {
public int[] maxDistance(int V, int src,
ArrayList<ArrayList<Integer>> edges) {
// Create adjacency list
ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
for (int i = 0; i < V; i++) {
graph.add(new ArrayList<>());
}
// Store edges
for (ArrayList<Integer> edge : edges) {
int u = edge.get(0);
int v = edge.get(1);
int w = edge.get(2);
graph.get(u).add(new int[]{v, w});
}
// Find topological order
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs(i, graph, visited, stack);
}
}
// Initialize distances
int[] dist = new int[V];
Arrays.fill(dist, Integer.MIN_VALUE);
// Source distance is 0
dist[src] = 0;
// Process vertices in topological order
while (!stack.isEmpty()) {
int u = stack.pop();
// Ignore unreachable vertices
if (dist[u] == Integer.MIN_VALUE) {
continue;
}
// Relax all outgoing edges
for (int[] edge : graph.get(u)) {
int v = edge[0];
int weight = edge[1];
dist[v] = Math.max(
dist[v],
dist[u] + weight
);
}
}
return dist;
}
private void dfs(
int u,
ArrayList<ArrayList<int[]>> graph,
boolean[] visited,
Stack<Integer> stack) {
visited[u] = true;
for (int[] edge : graph.get(u)) {
int v = edge[0];
if (!visited[v]) {
dfs(v, graph, visited, stack);
}
}
stack.push(u);
}
}
6. Building the Adjacency List
The input is:
[0, 1, 1]
which means:
0 → 1
weight = 1
We store it as:
graph.get(u).add(new int[]{v, w});
So:
graph.get(0)
contains:
{1, 1}
{2, 1}
for the first example.
The adjacency list represents:
0 → (1,1), (2,1)
1 → (2,5)
2 → nothing
3 → (1,2), (2,-1)
7. Finding Topological Order
We use DFS.
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
The visited array prevents visiting the same vertex multiple times.
We run DFS from every vertex:
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs(i, graph, visited, stack);
}
}
This is important because the graph may contain disconnected components.
8. DFS Function
The DFS function is:
private void dfs(
int u,
ArrayList<ArrayList<int[]>> graph,
boolean[] visited,
Stack<Integer> stack) {
visited[u] = true;
for (int[] edge : graph.get(u)) {
int v = edge[0];
if (!visited[v]) {
dfs(v, graph, visited, stack);
}
}
stack.push(u);
}
Notice this line:
stack.push(u);
It happens after visiting all adjacent vertices.
This is called post-order processing.
For example:
0 → 1 → 2
DFS visits:
0
↓
1
↓
2
Vertices are pushed:
2
1
0
When we pop the stack, we get:
0
1
2
which is the topological order.
9. Initializing the Distance Array
We need to represent unreachable vertices.
Therefore:
Arrays.fill(dist, Integer.MIN_VALUE);
For four vertices:
[-INF, -INF, -INF, -INF]
Then:
dist[src] = 0;
If:
src = 0
we get:
[0, -INF, -INF, -INF]
This means:
0 → 0 = 0
and currently every other vertex is unreachable.
10. Processing Topological Order
Now we process:
while (!stack.isEmpty()) {
int u = stack.pop();
Suppose the topological order is:
0 → 3 → 1 → 2
When we process vertex 0, its distance is:
dist[0] = 0
For edge:
0 → 1
weight = 1
we calculate:
0 + 1 = 1
So:
dist[1] = 1
For:
0 → 2
weight = 1
we calculate:
0 + 1 = 1
So:
dist[2] = 1
11. Why Do We Use Math.max()?
This is the most important part of the problem.
For the shortest path problem, we normally use:
Math.min()
But here we need the longest path.
Therefore we use:
Math.max()
The code is:
dist[v] = Math.max(
dist[v],
dist[u] + weight
);
Suppose we already have:
dist[2] = 1
and then find another path:
0 → 1 → 2
with distance:
1 + 5 = 6
We compare:
max(1, 6)
Result:
6
Therefore:
dist[2] = 6
12. Why Do We Skip Unreachable Vertices?
We have:
if (dist[u] == Integer.MIN_VALUE) {
continue;
}
This is very important.
Suppose:
src = 0
and vertex 3 cannot be reached.
Then:
dist[3] = Integer.MIN_VALUE
We should not calculate:
Integer.MIN_VALUE + weight
because that would produce an incorrect distance.
So we simply skip it.
13. Complete Dry Run
Input:
V = 4
src = 0
edges = [
[0,1,1],
[0,2,1],
[1,2,5],
[3,1,2],
[3,2,-1]
]
Initial:
dist = [0, -INF, -INF, -INF]
Process vertex 0:
0 → 1 = 1
0 → 2 = 1
Now:
dist = [0, 1, 1, -INF]
Process vertex 1:
1 → 2 = 5
Calculate:
dist[1] + 5
= 1 + 5
= 6
Compare:
max(1, 6) = 6
Now:
dist = [0, 1, 6, -INF]
Vertex 3 is unreachable, so it remains:
-INF
Final result:
[0, 1, 6, INF]
14. Second Example
Input:
V = 5
src = 1
edges = [
[0,1,1],
[0,2,2],
[1,4,4],
[3,2,-1],
[4,2,3],
[4,3,6]
]
Starting from:
1
We have:
1 → 4
Distance:
4
Then:
4 → 2
Distance:
4 + 3 = 7
And:
4 → 3
Distance:
4 + 6 = 10
From 3:
3 → 2
weight = -1
Distance:
10 - 1 = 9
Therefore:
[INF, 0, 9, 10, 4]
Notice that the path:
1 → 4 → 3 → 2
has distance:
4 + 6 - 1 = 9
15. Important Point About Negative Weights
This problem can contain negative edge weights:
-100 ≤ w ≤ 100
For example:
4 → 3 = 6
3 → 2 = -1
This is not a problem.
Because the graph is a DAG, we don't need Dijkstra's algorithm.
Topological-order DP works with:
Positive weights
Zero weights
Negative weights
16. Why Not Dijkstra?
Dijkstra's algorithm is designed for shortest paths with non-negative weights.
This problem can contain negative weights.
Therefore, Dijkstra is not the appropriate solution.
For a DAG, topological sorting gives us a much simpler solution:
Topological Sort
↓
Dynamic Programming
↓
Longest Distance
17. Why Not Bellman-Ford?
Bellman-Ford can handle negative weights, but its complexity is:
O(V × E)
The expected complexity for this problem is:
O(V + E)
Because the graph is a DAG, topological sorting allows us to solve it much faster.
18. Complexity Analysis
Time Complexity
Building the graph:
O(E)
DFS:
O(V + E)
Processing all edges:
O(V + E)
Overall:
O(V + E)
Space Complexity
Adjacency list:
O(V + E)
Visited array:
O(V)
Distance array:
O(V)
Stack:
O(V)
Overall auxiliary space is commonly stated as:
O(V + E)
with O(V) additional DP/visited/stack storage.
19. The Key Formula
The entire longest-path DP is based on this formula:
dist[v] = max(dist[v], dist[u] + weight)
For every edge:
u → v
with weight w:
dist[v] = Math.max(dist[v], dist[u] + w);
That is the main idea you should remember.
20. Easy Way to Remember the Solution
For Longest Path in DAG, remember:
DAG
↓
Topological Sort
↓
Initialize dist with -INF
↓
dist[src] = 0
↓
Process topological order
↓
Math.max()
↓
Answer
The most important difference from the shortest-path version is:
// Shortest path
dist[v] = Math.min(dist[v], dist[u] + weight);
// Longest path
dist[v] = Math.max(dist[v], dist[u] + weight);
So the problem is essentially topological sorting + dynamic programming.