10.8 Finding Shortest Paths in Directed Acyclic Graphs

Many shortest-path algorithms are designed to handle arbitrary graphs. They must deal with cycles, repeated visits, and complex path structures. Directed acyclic graphs (DAGs) are different. Since DAGs contain no cycles, shortest paths become significantly easier to compute.

In fact, shortest paths in a DAG can be found in linear time.

This is faster than Dijkstra, faster than Bellman-Ford, and often simpler to implement. The absence of cycles removes many of the difficulties that make general shortest-path problems challenging.

This recipe shows how to exploit topological ordering to compute shortest paths efficiently in weighted DAGs.

Problem

Given a weighted directed acyclic graph and a source vertex, compute the shortest distance to every reachable vertex.

Consider the following graph:

      5
  A -----> B
  |         \\n  |2         \1
  |           \\n  v            v
  C -----> D -----> E
      3        2

Starting from A, determine the minimum path cost to every vertex.

Unlike Dijkstra, edge weights may be negative as long as no cycles exist.

Solution

The algorithm consists of two phases:

1. Compute a topological ordering.
2. Process vertices in topological order while relaxing outgoing edges.

package main

import "fmt"

type Edge struct {
	To     int
	Weight int
}

func shortestPathDAG(graph [][]Edge, source int) []int {
	const INF = int(1e18)

	n := len(graph)

	visited := make([]bool, n)
	order := make([]int, 0, n)

	var dfs func(int)

	dfs = func(v int) {
		visited[v] = true

		for _, edge := range graph[v] {
			if !visited[edge.To] {
				dfs(edge.To)
			}
		}

		order = append(order, v)
	}

	for v := 0; v < n; v++ {
		if !visited[v] {
			dfs(v)
		}
	}

	for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 {
		order[i], order[j] = order[j], order[i]
	}

	dist := make([]int, n)

	for i := range dist {
		dist[i] = INF
	}

	dist[source] = 0

	for _, v := range order {
		if dist[v] == INF {
			continue
		}

		for _, edge := range graph[v] {
			candidate := dist[v] + edge.Weight

			if candidate < dist[edge.To] {
				dist[edge.To] = candidate
			}
		}
	}

	return dist
}

func main() {
	graph := [][]Edge{
		{{1, 5}, {2, 2}},
		{{4, 1}},
		{{3, 3}},
		{{4, 2}},
		{},
	}

	fmt.Println(shortestPathDAG(graph, 0))
}

Output:

[0 5 2 5 6]

The shortest path to vertex E has cost:

A -> B -> E

with total cost:

5 + 1 = 6

Understanding Topological Order

A topological ordering arranges vertices so that every edge points forward.

For example:

A -> B
A -> C
C -> D
B -> E
D -> E

One valid topological order is:

A C B D E

Every edge moves from left to right.

No edge ever points backward.

This property is possible only because DAGs contain no cycles.

The ordering guarantees that when a vertex is processed, every path that can reach it has already been considered.

Why This Solves Shortest Paths

Suppose we process vertices in topological order.

A
C
B
D
E

When processing:

D

every possible predecessor of D has already been processed.

No future vertex can create a new path back to D.

That would require a cycle.

Consequently, once all incoming edges have been relaxed, the distance to D is final.

This reasoning applies to every vertex.

The algorithm effectively performs a single forward sweep through the graph.

Visualizing the Relaxations

Consider:

A -> B = 4
A -> C = 1
C -> B = 2

Initial distances:

A = 0
B = ∞
C = ∞

Process A:

A = 0
B = 4
C = 1

Process C:

candidate = 1 + 2 = 3

Update:

B = 3

Process B:

No further changes.

Final result:

A = 0
B = 3
C = 1

The shortest path to B is:

A -> C -> B

rather than the direct edge.

Supporting Negative Edges

A useful property of DAG shortest paths is support for negative edge weights.

Consider:

A -> B = 5
A -> C = 2
C -> B = -4

The shortest path becomes:

A -> C -> B

with cost:

2 + (-4) = -2

Dijkstra cannot safely process this graph.

The DAG algorithm handles it naturally.

The reason is simple:

No cycles exist.

Without cycles, negative weights cannot produce endlessly improving paths.

The topological ordering remains valid.

Path Reconstruction

As with Dijkstra and Bellman-Ford, store predecessors during relaxation.

parent := make([]int, n)

for i := range parent {
	parent[i] = -1
}

Whenever a shorter path is found:

dist[next] = candidate
parent[next] = current

After processing finishes, reconstruct paths by following parent links backward.

This produces the actual shortest route rather than only its cost.

Comparison with Dijkstra

Suppose:

V = 1,000,000
E = 2,000,000

Dijkstra requires:

O((V + E) log V)

operations.

A DAG shortest-path algorithm requires:

O(V + E)

operations.

The difference can be substantial for large graphs.

Whenever the graph is known to be acyclic, exploiting that structure is usually worthwhile.

Discussion

The algorithm combines two important ideas:

• Topological sorting
• Edge relaxation

The topological sort removes the need for repeated processing.

The relaxation step remains identical to Bellman-Ford and Dijkstra.

This demonstrates an important principle in graph algorithms:

Relaxation is often the core operation. Different shortest-path algorithms differ primarily in the order in which relaxations occur.

Bellman-Ford relaxes all edges repeatedly.

Dijkstra relaxes edges in increasing distance order.

DAG shortest paths relax edges in topological order.

The underlying operation remains the same.

Complexity

Let:

• V = number of vertices
• E = number of edges

Topological sorting:

O(V + E)

Shortest-path computation:

O(E)

Total:

Operation	Complexity
Topological sort	O(V + E)
Relaxation pass	O(E)
Total runtime	O(V + E)
Memory usage	O(V + E)

This is optimal for graph traversal problems because every vertex and edge must be examined at least once.

Common Mistakes

Do not apply this algorithm to arbitrary directed graphs.

Topological ordering exists only for DAGs.

Do not assume all DFS orders are topological orders. The vertices must be processed in reverse finishing order.

Do not ignore disconnected components when constructing the ordering.

Do not reject negative edge weights automatically. They are perfectly valid in DAGs.

Do not forget reachability checks:

if dist[v] == INF {
	continue
}

Otherwise arithmetic involving infinity values may produce incorrect results.

Practical Applications

DAG shortest paths appear in:

• Build systems
• Dependency resolution
• Workflow orchestration
• Project scheduling
• Data processing pipelines
• Compiler optimization passes
• Task execution graphs
• Manufacturing workflows

Many real-world dependency graphs are naturally acyclic, making this algorithm especially useful.

Takeaway

Directed acyclic graphs permit a much simpler shortest-path solution than general graphs. By processing vertices in topological order, every vertex is finalized exactly once, producing shortest paths in linear time. The algorithm supports negative edge weights, avoids priority queues entirely, and illustrates how exploiting graph structure can lead to dramatically more efficient solutions.