Topological sort & Dijkstra

Order tasks so every dependency comes first, detect cycles, and find cheapest paths in weighted graphs with a heap.

Topological sort#

A topological order of a directed graph lists every node so that each edge u → v has u before v. It exists only if the graph has no cycle (a directed acyclic graph, or DAG). Build systems, package managers, spreadsheet recalculation and course planners all do this. Go itself orders package initialization this way.

Kahn's algorithm

Count each node's in-degree (incoming edges = unmet prerequisites).
Queue every node with in-degree 0: they can go first.
Repeatedly take a node from the queue, add it to the order, and "remove" its outgoing edges by decrementing each neighbor's in-degree. A neighbor that reaches 0 joins the queue.
If the order contains every node, it is valid. If not, the leftovers are stuck on a cycle.

Trace with 4 courses and prerequisites 1 needs 0, 2 needs 0, 3 needs 1, 3 needs 2 (edges 0→1, 0→2, 1→3, 2→3):

step	take	decrement	in-degrees (0,1,2,3)	queue	order
start			0, 1, 1, 2	[0]
1	0	1, 2	0, 0, 0, 2	[1 2]	0
2	1	3	0, 0, 0, 1	[2]	0 1
3	2	3	0, 0, 0, 0	[3]	0 1 2
4	3			[]	0 1 2 3

All 4 processed: valid. Add an edge 3 → 0 and node 0 starts with in-degree 1; nothing ever enters the queue, and the cycle is detected.

Run the trace

The program runs Kahn's algorithm on the courses above, then again with the extra edge 3 → 0:

kahn_trace.go

package main
 
import "fmt"
 
func topo(n int, edges [][2]int) []int {
	adj := make([][]int, n)
	indeg := make([]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
		indeg[e[1]]++
	}
	var queue, order []int
	for u := range n {
		if indeg[u] == 0 {
			queue = append(queue, u)
		}
	}
	fmt.Printf("  start: in-degrees %v queue %v\n", indeg, queue)
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		order = append(order, u)
		for _, v := range adj[u] {
			indeg[v]--
			if indeg[v] == 0 {
				queue = append(queue, v)
			}
		}
		fmt.Printf("  take %d: in-degrees %v queue %v order %v\n", u, indeg, queue, order)
	}
	return order
}
 
func main() {
	edges := [][2]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}}
	fmt.Println("courses:")
	order := topo(4, edges)
	fmt.Println("  valid:", len(order) == 4)
 
	fmt.Println("with 3 -> 0:")
	order = topo(4, append(edges, [2]int{3, 0}))
	fmt.Println("  valid:", len(order) == 4, "(stuck on a cycle)")
}

Output

courses:
  start: in-degrees [0 1 1 2] queue [0]
  take 0: in-degrees [0 0 0 2] queue [1 2] order [0]
  take 1: in-degrees [0 0 0 1] queue [2] order [0 1]
  take 2: in-degrees [0 0 0 0] queue [3] order [0 1 2]
  take 3: in-degrees [0 0 0 0] queue [] order [0 1 2 3]
  valid: true
with 3 -> 0:
  start: in-degrees [1 1 1 2] queue []
  valid: false (stuck on a cycle)

Step through it

Add deploy>go to create a cycle and watch the algorithm get stuck.

InteractiveTopological sort (Kahn's algorithm)Repeatedly take a node with no remaining prerequisites. If some nodes are never freed, there is a cycle.

queue

lint

order

–

	build	deploy	go	lint	test
in-degree	1	2	0	0	2

Count incoming edges. Nodes with in-degree 0 (go, lint) have no prerequisites and start in the queue.

1 / 7

Dijkstra's algorithm#

BFS finds fewest edges. With weights, the path with fewer edges may cost more. Dijkstra generalizes BFS: instead of a queue, it uses a min-heap keyed by distance, so it always expands the closest node not yet finalized.

dist[src] = 0, every other distance infinity. Push (src, 0).
Pop the node with the smallest distance. If this entry is outdated (we already found a cheaper way), skip it.
For each edge u → v with weight w: if dist[u] + w < dist[v], we found a cheaper way to v (relaxation): update dist[v] and push (v, dist[v]).

Trace on this graph from A:

A --4--> B
A --1--> C
C --2--> B
B --1--> D
C --5--> D

pop (node, dist)	relax edges	dist A, B, C, D	heap after
(A, 0)	B = 4, C = 1	0, 4, 1, ∞	(C,1) (B,4)
(C, 1)	B: 1+2 = 3 < 4, update; D = 6	0, 3, 1, 6	(B,3) (B,4) (D,6)
(B, 3)	D: 3+1 = 4 < 6, update	0, 3, 1, 4	(B,4) (D,4) (D,6)
(B, 4)	stale (4 > 3): skip		(D,4) (D,6)
(D, 4)	none	0, 3, 1, 4	(D,6)
(D, 6)	stale: skip

Cheapest A→D is 4 via A→C→B→D, even though A→B→D uses fewer edges.

Why it works: when a node is popped with its smallest distance, every other path to it would have to go through nodes that are at least as far, and with non-negative weights those cannot make it cheaper. A negative edge breaks this reasoning; use Bellman-Ford (relax every edge n-1 times) for those graphs.

Run the trace

The same graph with nodes A–D numbered 0–3. The program also keeps prev[v], the node we came from on the cheapest known path, so it can print the route at the end:

dijkstra_trace.go

package main
 
import (
	"container/heap"
	"fmt"
	"math"
)
 
type item struct{ node, dist int }
type H []item
 
func (h H) Len() int           { return len(h) }
func (h H) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h H) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *H) Push(x any)        { *h = append(*h, x.(item)) }
func (h *H) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}
 
const inf = math.MaxInt
 
func main() {
	name := "ABCD"
	type edge struct{ to, w int }
	adj := [][]edge{
		0: {{1, 4}, {2, 1}}, // A->B 4, A->C 1
		1: {{3, 1}},         // B->D 1
		2: {{1, 2}, {3, 5}}, // C->B 2, C->D 5
		3: {},
	}
	dist := []int{0, inf, inf, inf}
	prev := []int{-1, -1, -1, -1}
	h := &H{{0, 0}}
	for h.Len() > 0 {
		it := heap.Pop(h).(item)
		if it.dist > dist[it.node] {
			fmt.Printf("pop (%c,%d): stale, skip\n", name[it.node], it.dist)
			continue
		}
		fmt.Printf("pop (%c,%d):", name[it.node], it.dist)
		for _, e := range adj[it.node] {
			if nd := it.dist + e.w; nd < dist[e.to] {
				dist[e.to], prev[e.to] = nd, it.node
				heap.Push(h, item{e.to, nd})
				fmt.Printf(" %c=%d", name[e.to], nd)
			}
		}
		fmt.Println()
	}
 
	route := "D"
	for v := prev[3]; v != -1; v = prev[v] {
		route = string(name[v]) + "->" + route
	}
	fmt.Println("cheapest A->D:", dist[3], "via", route)
}

Output

pop (A,0): B=4 C=1
pop (C,1): B=3 D=6
pop (B,3): D=4
pop (B,4): stale, skip
pop (D,4):
pop (D,6): stale, skip
cheapest A->D: 4 via A->C->B->D

Step through it

InteractiveDijkstra's shortest pathsAlways expand the closest unfinished node, and relax its edges. Stale heap entries are skipped.

heap

(A,0)

	A	B	C	D	E
dist	0	∞	∞	∞	∞
via	–	–	–	–	–

dist[A] = 0, everything else ∞. The heap holds (A, 0).

1 / 10

The full program#

paths.go

package main
 
import (
	"container/heap"
	"fmt"
	"math"
)
 
func topoSort(n int, edges [][2]int) ([]int, bool) {
	adj := make([][]int, n)
	indeg := make([]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
		indeg[e[1]]++
	}
	var q []int
	for v, d := range indeg {
		if d == 0 {
			q = append(q, v)
		}
	}
	var order []int
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		order = append(order, u)
		for _, v := range adj[u] {
			indeg[v]--
			if indeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	return order, len(order) == n
}
 
type item struct{ node, dist int }
type pq []item
 
func (h pq) Len() int           { return len(h) }
func (h pq) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h pq) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *pq) Push(x any)        { *h = append(*h, x.(item)) }
func (h *pq) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}
 
type edge struct{ to, w int }
 
func dijkstra(adj [][]edge, src int) []int {
	dist := make([]int, len(adj))
	for i := range dist {
		dist[i] = math.MaxInt
	}
	dist[src] = 0
	h := &pq{{src, 0}}
	for h.Len() > 0 {
		cur := heap.Pop(h).(item)
		if cur.dist > dist[cur.node] {
			continue // stale entry
		}
		for _, e := range adj[cur.node] {
			if nd := cur.dist + e.w; nd < dist[e.to] {
				dist[e.to] = nd
				heap.Push(h, item{e.to, nd})
			}
		}
	}
	return dist
}
 
func main() {
	order, ok := topoSort(4, [][2]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}})
	fmt.Println(order, ok)
	_, ok = topoSort(4, [][2]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 0}})
	fmt.Println("with cycle:", ok)
 
	const A, B, C, D = 0, 1, 2, 3
	adj := make([][]edge, 4)
	adj[A] = []edge{{B, 4}, {C, 1}}
	adj[C] = []edge{{B, 2}, {D, 5}}
	adj[B] = []edge{{D, 1}}
	fmt.Println("dist from A:", dijkstra(adj, A))
 
	unreachable := dijkstra([][]edge{{}, {}}, 0)
	fmt.Println("unreachable is MaxInt:", unreachable[1] == math.MaxInt)
}

Output

[0 1 2 3] true
with cycle: false
dist from A: [0 3 1 4]
unreachable is MaxInt: true

Complexity#

Algorithm	Time	Space
Kahn's topological sort	O(n + m)	O(n + m)
Dijkstra with a binary heap	O((n + m) log n)	O(n + m)
Bellman-Ford	O(n · m)	O(n)

Recognizing the pattern#

"prerequisites", "dependencies", "order of tasks", "can all be finished": topological sort.
"cheapest", "minimum time", "minimum cost" with different non-negative edge costs: Dijkstra.
All edges cost the same: plain BFS is enough and faster.
Negative costs, or a limit on the number of edges used: Bellman-Ford.

Summary#

Topological order puts every dependency first; it exists only in DAGs.
Kahn's algorithm: queue in-degree-0 nodes; fewer than n processed means a cycle.
Dijkstra: min-heap by distance, relax edges, skip stale entries; non-negative weights only.
Pick BFS for equal weights, Dijkstra for non-negative weights, Bellman-Ford for negative weights.

Topological sort & Dijkstra