Advanced Graphs · Dijkstra & Spanning Trees

One-liner: when the edges of a graph have costs, ask which cost you are minimizing — the cheapest route from one place (Dijkstra), the cheapest way to connect everything (a spanning tree), or a valid ordering (topological sort) — and let a heap pick the next best step.

The analogy

Think of a road map with a toll on every road. BFS counts roads, but you care about money, so the route with the fewest roads is no longer the cheapest. Dijkstra works like a patient traveller: always walk to the closest unfinished town next, because a closer town can never be reached cheaper later. A spanning tree is a different job: you are the telecom company laying the least total cable that connects every town, and you do not care about routes at all.

Recognition signals

Edges carry a weight: time, price, distance, effort.
You want the cheapest path from one node (Dijkstra), or the cheapest path with a limit on the number of edges (Bellman-Ford rounds).
You want the cheapest way to connect all nodes with no loops (Prim or Kruskal, a minimum spanning tree).
The cost of a path is the maximum edge or cell on it, not the sum (Dijkstra with max instead of +).
You must use every edge once (Eulerian path, Hierholzer), or derive an order from pairwise rules (topological sort).

Step-by-step walkthrough (Dijkstra)

Nodes 0..3, edges 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1). Start at 0.

Heap holds (node 0, dist 0). Pop it. Relax 0→1 to 4 and 0→2 to 1.
The closest unfinished node is 2 (dist 1). Pop it. Relax 2→1: 1 + 2 = 3, better than 4, so update.
Pop 1 (dist 3). Relax 1→3 to 4.
Pop 1 again with the old dist 4 — it is stale (we already know 3), skip it.
Pop 3 (dist 4). Done: distances [0, 3, 1, 4].

Code template

Dijkstra in Go with container/heap. The three numbered comments are the whole algorithm.

Dijkstra — go/advancedgraphs/advanced.go

// Edge is a weighted, directed edge to node To.
type Edge struct{ To, W int }

type item struct{ node, dist int }
type minHeap []item

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// Dijkstra returns the shortest distance from src to every node (math.MaxInt if unreachable).
// It only works when no edge weight is negative.
func Dijkstra(graph [][]Edge, src int) []int {
	dist := make([]int, len(graph))
	for i := range dist {
		dist[i] = math.MaxInt
	}
	dist[src] = 0
	h := &minHeap{{src, 0}}
	for h.Len() > 0 {
		cur := heap.Pop(h).(item) // 1. always expand the closest unfinished node
		if cur.dist > dist[cur.node] {
			continue // 2. stale entry: a shorter path was found after this was pushed
		}
		for _, e := range graph[cur.node] {
			if nd := cur.dist + e.W; nd < dist[e.To] { // 3. relax the edge
				dist[e.To] = nd
				heap.Push(h, item{e.To, nd})
			}
		}
	}
	return dist
}

Watch it run on the walkthrough graph, then on a bigger one. Note the moment an outdated heap entry is skipped.

Dijkstra — cheapest path from one nodeedges; start =

∞

node: —
heap: (0, 0)

dist holds the best known distance from node 0. Everything starts at ∞ except the start (0). The heap holds (node, distance) pairs.

// Edge is a weighted, directed edge to node To.
type Edge struct{ To, W int }

type item struct{ node, dist int }
type minHeap []item

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// Dijkstra returns the shortest distance from src to every node (math.MaxInt if unreachable).
// It only works when no edge weight is negative.
func Dijkstra(graph [][]Edge, src int) []int {
	dist := make([]int, len(graph))
	for i := range dist {
		dist[i] = math.MaxInt
	}
	dist[src] = 0
	h := &minHeap{{src, 0}}
	for h.Len() > 0 {
		cur := heap.Pop(h).(item) // 1. always expand the closest unfinished node
		if cur.dist > dist[cur.node] {
			continue // 2. stale entry: a shorter path was found after this was pushed
		}
		for _, e := range graph[cur.node] {
			if nd := cur.dist + e.W; nd < dist[e.To] { // 3. relax the edge
				dist[e.To] = nd
				heap.Push(h, item{e.To, nd})
			}
		}
	}
	return dist
}

1/34

Why each part exists:

1cur := heap.Pop(h).(item)

Why:

The heap always hands you the closest node not yet finished. Once a node is popped with its best distance, no later path can beat it, as long as no edge is negative.

2if cur.dist > dist[cur.node] { continue }

Why:

A node can be pushed several times with different distances. Go's heap has no "decrease key", so we push a new entry and skip the outdated ones when they come out.

3if nd := cur.dist + e.W; nd < dist[e.To]

Why:

Relaxing an edge: is going through this node a cheaper way to reach the neighbour? If yes, record it and push it.

The real solutions

Network Delay Time — run Dijkstra and take the farthest node; unreachable means -1:

NetworkDelayTime

// NetworkDelayTime: times[i] = {from, to, weight}, nodes are 1..n.
// The signal reaches everyone when it reaches the farthest node.
func NetworkDelayTime(times [][]int, n, k int) int {
	graph := make([][]Edge, n+1)
	for _, t := range times {
		graph[t[0]] = append(graph[t[0]], Edge{t[1], t[2]})
	}
	dist := Dijkstra(graph, k)
	worst := 0
	for node := 1; node <= n; node++ {
		if dist[node] == math.MaxInt {
			return -1
		}
		worst = max(worst, dist[node])
	}
	return worst
}

Min Cost to Connect All Points — a minimum spanning tree with Prim's algorithm. Grow one tree and always attach the cheapest outside point:

MinCostConnectPoints

// MinCostConnectPoints: minimum spanning tree with Prim's algorithm.
// Grow one tree: repeatedly attach the point that is cheapest to reach from the tree.
func MinCostConnectPoints(points [][]int) int {
	n := len(points)
	dist := make([]int, n) // cheapest known cost to attach each point to the tree
	for i := range dist {
		dist[i] = math.MaxInt
	}
	inTree := make([]bool, n)
	dist[0] = 0
	total := 0
	for range n {
		best := -1
		for i := 0; i < n; i++ {
			if !inTree[i] && (best == -1 || dist[i] < dist[best]) {
				best = i
			}
		}
		inTree[best] = true
		total += dist[best]
		for i := 0; i < n; i++ {
			if !inTree[i] {
				d := abs(points[best][0]-points[i][0]) + abs(points[best][1]-points[i][1])
				dist[i] = min(dist[i], d)
			}
		}
	}
	return total
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

With a complete graph of n points this array version is O(n²), which beats building a heap of all n² edges. Kruskal's algorithm (sort edges, add one if Union-Find says it joins two groups) is the alternative.

Cheapest Flights Within K Stops — a stop limit breaks plain Dijkstra, so relax every edge in rounds, one round per flight:

FindCheapestPrice

// FindCheapestPrice: cheapest src→dst price with at most k stops.
// Bellman-Ford limited to k+1 rounds. Each round reads the PREVIOUS round's prices, so one round = one more flight.
func FindCheapestPrice(n int, flights [][]int, src, dst, k int) int {
	prices := make([]int, n)
	for i := range prices {
		prices[i] = math.MaxInt
	}
	prices[src] = 0
	for range k + 1 {
		next := append([]int(nil), prices...)
		for _, f := range flights {
			from, to, cost := f[0], f[1], f[2]
			if prices[from] != math.MaxInt && prices[from]+cost < next[to] {
				next[to] = prices[from] + cost
			}
		}
		prices = next
	}
	if prices[dst] == math.MaxInt {
		return -1
	}
	return prices[dst]
}

Reading from prices but writing to next is the important detail: it stops one round from using two flights.

Reconstruct Itinerary — use every ticket exactly once (an Eulerian path). Visit the smallest destination first, and add an airport to the answer only when it has no tickets left; reverse at the end:

FindItinerary

// FindItinerary: use every ticket once, smallest airport name first (Hierholzer's algorithm).
func FindItinerary(tickets [][]string) []string {
	adj := map[string][]string{}
	for _, t := range tickets {
		adj[t[0]] = append(adj[t[0]], t[1])
	}
	for from := range adj {
		sort.Sort(sort.Reverse(sort.StringSlice(adj[from]))) // reversed so popping the end gives the smallest
	}
	var route []string
	var visit func(string)
	visit = func(airport string) {
		for len(adj[airport]) > 0 {
			next := adj[airport][len(adj[airport])-1]
			adj[airport] = adj[airport][:len(adj[airport])-1]
			visit(next)
		}
		route = append(route, airport) // added only once stuck: dead ends end up at the back
	}
	visit("JFK")
	for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
		route[i], route[j] = route[j], route[i]
	}
	return route
}

Alien Dictionary — adjacent words give ordering rules between letters; a topological sort turns them into an order, and a cycle means the input is contradictory:

AlienOrder

// AlienOrder: letter order implied by a sorted list of words, or "" if it is contradictory.
func AlienOrder(words []string) string {
	next := map[byte]map[byte]bool{}
	indeg := map[byte]int{}
	for _, w := range words {
		for i := 0; i < len(w); i++ {
			if _, ok := indeg[w[i]]; !ok {
				indeg[w[i]] = 0
				next[w[i]] = map[byte]bool{}
			}
		}
	}
	for i := 0; i+1 < len(words); i++ {
		a, b := words[i], words[i+1]
		if len(a) > len(b) && a[:len(b)] == b {
			return "" // "abc" can never come before "ab"
		}
		for j := 0; j < len(a) && j < len(b); j++ {
			if a[j] != b[j] { // the first difference is the only rule this pair gives us
				if !next[a[j]][b[j]] {
					next[a[j]][b[j]] = true
					indeg[b[j]]++
				}
				break
			}
		}
	}
	var queue []byte
	for c := 'a'; c <= 'z'; c++ { // fixed scan order keeps the output deterministic
		if d, ok := indeg[byte(c)]; ok && d == 0 {
			queue = append(queue, byte(c))
		}
	}
	var out []byte
	for len(queue) > 0 {
		c := queue[0]
		queue = queue[1:]
		out = append(out, c)
		var outs []byte
		for to := range next[c] {
			outs = append(outs, to)
		}
		sort.Slice(outs, func(i, j int) bool { return outs[i] < outs[j] })
		for _, to := range outs {
			if indeg[to]--; indeg[to] == 0 {
				queue = append(queue, to)
			}
		}
	}
	if len(out) != len(indeg) {
		return "" // a cycle: some letters never reached in-degree 0
	}
	return string(out)
}

Swim in Rising Water is Dijkstra where the cost of a path is the largest cell on it: push max(current, neighbour) instead of adding.

Complexity

Approach	Time	Space
Dijkstra with a binary heap	O(E log V)	O(V + E)
Bellman-Ford limited to k rounds	O(k · E)	O(V)
Prim (array) / Kruskal (sort + Union-Find)	O(V²) / O(E log E)	O(V)
Topological sort (Kahn)	O(V + E)	O(V + E)

Common mistakes

Practice ladder

1.
Network Delay Time
Cheapest path from one source to everyone.
Medium
2.
Min Cost to Connect All Points
Connect everything, no cycles, least total.
Medium
3.
Cheapest Flights Within K Stops
A limit on edges changes the algorithm.
Medium
4.
Path With Minimum Effort
A path costs its largest step, not the sum.
Medium
5.
Swim in Rising Water
Hard
6.
Reconstruct Itinerary
Every ticket exactly once.
Hard
7.
Alien Dictionary
Where do the ordering rules come from?
Hard

Which pattern? Drills

Question 1 of 5

A signal is sent from one server. Each cable has a different delay. How long until every server has received it?

Which pattern?