Graphs and dynamic programming · Lesson 20 of 23
Shortest paths, topological sort and union-find
Dijkstra for weights, Kahn for ordering tasks, and union-find for connected groups.
Dijkstra: shortest paths with positive weights
When edges have different costs (distances, times), BFS isn't enough. Dijkstra always takes the closest unfinished node (using a min-heap) and improves its neighbours' distances from it. With positive weights, the first time a node is taken its distance is final.
// Dijkstra with a simple array scan (O(V²)); a heap makes it O(E log V)
function dijkstra(n, edges, start) {
const adj = Array.from({ length: n }, () => [])
for (const [u, v, w] of edges) adj[u].push([v, w])
const dist = new Array(n).fill(Infinity), done = new Array(n).fill(false)
dist[start] = 0
for (let step = 0; step < n; step++) {
let u = -1
for (let i = 0; i < n; i++) if (!done[i] && (u < 0 || dist[i] < dist[u])) u = i
if (dist[u] === Infinity) break
done[u] = true
for (const [v, w] of adj[u]) if (dist[u] + w < dist[v]) dist[v] = dist[u] + w
}
return dist
}
console.log(dijkstra(4, [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5]], 0))- 1// Distances from 0 as Dijkstra finishes each node
- ▶let dist = [0, 4, 1, Infinity] // after taking 0
- 3dist = [0, 3, 1, 6] // after taking 2 (0→2→1 = 3, 0→2→3 = 6)
- 4dist = [0, 3, 1, 4] // after taking 1 (0→2→1→3 = 4)
- 5console.log(dist.join(" "))
Variables
| done | 0 |
| dist | [0, 4, 1, ∞] |
Output
From 0: node 1 costs 4, node 2 costs 1.
Topological sort: ordering things with prerequisites
// Kahn's algorithm: repeatedly take a task with no unmet prerequisites
function topoOrder(n, prereqs) { // [a, b] means b must come before a
const next = Array.from({ length: n }, () => []), need = new Array(n).fill(0)
for (const [a, b] of prereqs) { next[b].push(a); need[a]++ }
const ready = [], order = []
for (let i = 0; i < n; i++) if (need[i] === 0) ready.push(i)
while (ready.length) {
const t = ready.shift()
order.push(t)
for (const d of next[t]) if (--need[d] === 0) ready.push(d)
}
return order.length === n ? order : null // null: there's a cycle
}
console.log(topoOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]), topoOrder(2, [[0, 1], [1, 0]]))Union-find: "are these two in the same group?"
class UnionFind {
constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); this.groups = n }
find(x) {
while (this.parent[x] !== x) { this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x] } // path compression
return x
}
union(a, b) {
const ra = this.find(a), rb = this.find(b)
if (ra === rb) return false // already connected: this edge closes a cycle
this.parent[ra] = rb
this.groups--
return true
}
}
const uf = new UnionFind(5)
uf.union(0, 1); uf.union(3, 4)
console.log(uf.groups, uf.find(0) === uf.find(1), uf.union(1, 0))Quick question
You need to know whether each new edge creates a cycle in a growing undirected graph. The fastest tool?
Exercise
Use UnionFind (included) to find the first edge that closes a cycle. It must print 3,0.
Expected output: 3,0
class UnionFind {
constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i) }
find(x) { while (this.parent[x] !== x) { this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x] } return x }
union(a, b) { const ra = this.find(a), rb = this.find(b); if (ra === rb) return false; this.parent[ra] = rb; return true }
}
function firstCycleEdge(n, edges) {
}
console.log(String(firstCycleEdge(4, [[0, 1], [1, 2], [2, 3], [3, 0], [2, 0]])))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.