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:
Vvertices numbered from0toV - 1A directed weighted graph
edges[i] = [u, v, w]An edge from
utovwith weightwA 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:

Join the conversation! Your thoughts help the community grow.