☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Shortest path in DAG

Hard TUF ID 507 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a directed acyclic graph (DAG) with n nodes numbered 0 to n - 1 and a list of weighted edges, where {u, v, w} is an edge from u to v of weight w. Return the shortest distance from the source node (node 0 in the usual statement; the code takes src as a parameter) to every node. If a node cannot be reached, its distance is -1.

Constraints: 1 ≤ n ≤ 100, 1 ≤ m ≤ 100 edges, 0 ≤ w ≤ 100 in the original statement. The graph is guaranteed to have no directed cycle.

Example 1

n = 6
edges = [0→1 (2), 0→4 (1), 4→5 (4), 4→2 (2), 1→2 (3), 2→3 (6), 5→3 (1)]
answer = [0, 2, 3, 6, 1, 5]
// node 2: 0→4→2 costs 3, cheaper than 0→1→2 at 5
// node 3: 0→4→5→3 costs 6, cheaper than 0→4→2→3 at 9

Example 2

n = 4, edges = [0→1 (2), 0→2 (1)]
answer = [0, 2, 1, -1]   // nothing leads to node 3

Approach 1: Brute force, Bellman-Ford relaxation

Intuition. A correct distance array satisfies dist[v] ≤ dist[u] + w for every edge u → v. Start with dist[src] = 0 and infinity elsewhere, and repeatedly relax edges: whenever an edge breaks the rule, lower dist[v]. After the r-th sweep over all edges, every node whose shortest path has at most r edges is correct, because each sweep extends correct prefixes by one more edge. A shortest path has at most n - 1 edges, so n - 1 sweeps suffice. This is Bellman-Ford, and it works on any graph without negative cycles, not just DAGs.

Algorithm.

  1. Fill dist with infinity and set dist[src] = 0.
  2. Repeat up to n - 1 times: relax every edge whose tail has a finite distance. Stop early if a sweep changes nothing.
  3. Convert remaining infinities to -1.
static int[] bruteForce(int n, int[][] edges, int src) {
    final int INF = Integer.MAX_VALUE;
    int[] dist = new int[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 1; round < n; round++) {
        boolean changed = false;
        for (int[] e : edges) {
            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) {
                dist[e[1]] = dist[e[0]] + e[2];
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (int i = 0; i < n; i++) if (dist[i] == INF) dist[i] = -1;
    return dist;
}

Complexity. Time O(V × E): up to V - 1 sweeps over every edge. Space O(V) for the distances.

The waste is in the order. A sweep may relax the edges leaving u while dist[u] is still too large, so the work has to be redone in later sweeps once dist[u] improves.

Approach 2: Optimal, relax in topological order

Intuition. A DAG has a topological order: a list of the nodes in which every edge points from left to right. Process the nodes in that order and relax each node’s outgoing edges exactly once. When we reach u, every edge into u starts at a node that appears earlier in the list, so it has already been relaxed. dist[u] therefore already accounts for every way of arriving at u, it is final, and relaxing out of it once is enough.

More formally, take any shortest path src = x0 → x1 → ... → xk. Its nodes appear in increasing topological position. By induction, when x(i) is processed its distance is correct, and relaxing x(i) → x(i+1) makes dist[x(i+1)] correct before x(i+1) is processed.

So the whole algorithm is “topological sort, then one sweep”. We get the order from Kahn’s algorithm. The topo array doubles as Kahn’s queue, with head and tail as the queue’s ends. A DFS-based topological sort (push a node onto a stack after its descendants finish, then pop) works equally well.

Algorithm.

  1. Build the adjacency list of {target, weight} pairs and the in-degrees.
  2. Run Kahn’s algorithm to fill topo.
  3. Set dist[src] = 0, all others infinity.
  4. For each u in topo order: skip it if dist[u] is infinity (unreachable from src), otherwise relax every edge u → v.
  5. Convert remaining infinities to -1.
static int[] optimal(int n, int[][] edges, int src) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indegree = new int[n];
    for (int[] e : edges) {
        adj.get(e[0]).add(new int[]{e[1], e[2]});
        indegree[e[1]]++;
    }
    int[] topo = new int[n];                              // used as the queue of Kahn's algorithm
    int head = 0, tail = 0;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) topo[tail++] = i;
    while (head < tail) {
        int u = topo[head++];
        for (int[] e : adj.get(u)) {
            if (--indegree[e[0]] == 0) topo[tail++] = e[0];
        }
    }
    final int INF = Integer.MAX_VALUE;
    int[] dist = new int[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int u : topo) {                                  // all edges into u were relaxed before we get here
        if (dist[u] == INF) continue;                     // u is not reachable from src
        for (int[] e : adj.get(u)) {
            dist[e[0]] = Math.min(dist[e[0]], dist[u] + e[1]);
        }
    }
    for (int i = 0; i < n; i++) if (dist[i] == INF) dist[i] = -1;
    return dist;
}

Dry run on Example 1. Kahn’s algorithm gives the order [0, 1, 4, 5, 2, 3]. Relaxing in that order (v ← d means dist[v] is lowered to d):

u dist[u] relaxations dist after (0..5)
0 0 1 ← 2, 4 ← 1 0, 2, ∞, ∞, 1, ∞
1 2 2 ← 5 0, 2, 5, ∞, 1, ∞
4 1 5 ← 5, 2 ← 3 0, 2, 3, ∞, 1, 5
5 5 3 ← 6 0, 2, 3, 6, 1, 5
2 3 3: 9 is not better 0, 2, 3, 6, 1, 5
3 6 none 0, 2, 3, 6, 1, 5

Node 2 was first set to 5 through node 1 and corrected to 3 through node 4, and both happened before node 2 itself was processed, which is what the topological order guarantees.

Complexity. Time O(V + E): Kahn’s algorithm is linear, and the relaxation sweep touches each edge once. Space O(V + E) for the adjacency list, the in-degrees, topo and dist.

Why not Dijkstra?

Dijkstra’s algorithm would also work for non-negative weights, but it costs O((V + E) log V) because of the priority queue. The topological sweep is linear. More importantly, the DAG method does not care about the sign of the weights. Dijkstra declares a node final when it is the closest unfinished node, which a later negative edge can contradict. In a DAG no such surprise is possible: everything that could lower dist[u] comes earlier in the order. The test with edges 0→1 (5), 0→2 (2), 2→1 (-4) returns [0, -2, 2]. If you allow negative weights, though, pick an unreachable marker other than -1, since -1 could then be a genuine distance.

Longest paths are just as easy in a DAG: negate the weights, or use max instead of min. In a general graph that problem is NP-hard.

Edge cases and pitfalls