Graph type into a weighted graph, and how to drive a from-scratch Dijkstra with Zig's std.PriorityQueue (the binary heap you would otherwise write by hand);?u64 optional in stead of a magic sentinel, and where allocation errors ride along the happy path;std.ArrayList from episode 22 (we lean on both, and meet std.PriorityQueue for the first time);Learn Zig Series):Last episode I left you with a hint about dependency ordering, and we will get there -- but there is a more pressing debt to settle first, and it is hiding inside the shiny BFS shortest path we were so pleased with. That path finder answered "what is the fewest number of hops from here to there", and it did so beautifully, guaranteed optimal, in one clean sweep. But re-read the guarantee: fewest hops. It quietly assumes every edge is worth exactly one. The moment your edges carry a weight -- a road with a length, a network link with a latency, a flight with a price -- BFS is not just suboptimal, it is wrong. It will happily hand you a three-hop route costing 300 when a five-hop route costs 50, because it counts hops and cannot see cost. Today we fix that, and the fix has a name every programmer eventually needs: Dijkstra's algorithm. And once we have it, we bolt on a hunch and get A*, the same search with a sense of direction. But first -- the BFS debt from episode 119, all three exercises, in real compilable code ;-)
Exercise 1 -- multi-source BFS. The whole trick is in the seeding. A normal BFS starts with one vertex at distance zero in the queue; a multi-source BFS drops all the sources into the queue up front, every one of them at distance zero. From there the loop is byte-for-byte identical -- the wavefront just starts from several places at once and collides somewhere in the middle, so the first time any vertex is reached, it was reached from the nearest source. That is exactly how you answer "how far is every cell from the closest exit" in one pass in stead of running BFS once per exit:
const std = @import("std");
const Graph = struct {
gpa: std.mem.Allocator,
adj: std.ArrayList(std.ArrayList(usize)),
directed: bool,
fn init(gpa: std.mem.Allocator, n: usize, directed: bool) !Graph {
var adj: std.ArrayList(std.ArrayList(usize)) = .empty;
try adj.ensureTotalCapacity(gpa, n);
var i: usize = 0;
while (i < n) : (i += 1) adj.appendAssumeCapacity(.empty);
return .{ .gpa = gpa, .adj = adj, .directed = directed };
}
fn deinit(self: *Graph) void {
for (self.adj.items) |*list| list.deinit(self.gpa);
self.adj.deinit(self.gpa);
}
fn addEdge(self: *Graph, from: usize, to: usize) !void {
try self.adj.items[from].append(self.gpa, to);
if (!self.directed) try self.adj.items[to].append(self.gpa, from);
}
fn neighbors(self: *const Graph, v: usize) []const usize {
return self.adj.items[v].items;
}
};
fn bfsMultiSource(gpa: std.mem.Allocator, g: *const Graph, sources: []const usize) ![]i64 {
const n = g.adj.items.len;
const dist = try gpa.alloc(i64, n);
@memset(dist, -1);
var queue: std.ArrayList(usize) = .empty;
defer queue.deinit(gpa);
for (sources) |s| {
if (dist[s] == -1) {
dist[s] = 0;
try queue.append(gpa, s);
}
}
var head: usize = 0;
while (head < queue.items.len) {
const v = queue.items[head];
head += 1;
for (g.neighbors(v)) |nb| {
if (dist[nb] == -1) {
dist[nb] = dist[v] + 1;
try queue.append(gpa, nb);
}
}
}
return dist;
}
test "multi-source BFS gives distance to the nearest source" {
const gpa = std.testing.allocator;
var g = try Graph.init(gpa, 5, false);
defer g.deinit();
try g.addEdge(0, 1);
try g.addEdge(1, 2);
try g.addEdge(2, 3);
try g.addEdge(3, 4);
const dist = try bfsMultiSource(gpa, &g, &.{ 0, 4 });
defer gpa.free(dist);
try std.testing.expectEqual(@as(i64, 0), dist[0]);
try std.testing.expectEqual(@as(i64, 2), dist[2]); // middle: min(2 from 0, 2 from 4)
try std.testing.expectEqual(@as(i64, 0), dist[4]);
}
Keep that Graph in front of you -- the next two solutions build on it, and so does half of today's episode.
Exercise 2 -- bipartite check via BFS colouring. A graph is bipartite if you can split its vertices into two teams so that no edge falls inside a team -- every edge crosses between them. The BFS way to test that is delightfully direct: colour the start vertex 0, and colour every vertex you discover the opposite colour of whoever discovered it (1 - color[v] flips 0 to 1 and back). If you ever look at an edge whose two ends already carry the same colour, you have found an edge inside a team, and the graph is not bipartite. Note the for (0..n) outer loop -- a graph can be disconnected, so we have to try every uncoloured vertex as a fresh start, exactly the "cover a disconnected graph" pattern from last episode:
fn isBipartite(gpa: std.mem.Allocator, g: *const Graph) !bool {
const n = g.adj.items.len;
const color = try gpa.alloc(i8, n);
defer gpa.free(color);
@memset(color, -1); // -1 uncoloured
var queue: std.ArrayList(usize) = .empty;
defer queue.deinit(gpa);
for (0..n) |start| {
if (color[start] != -1) continue;
color[start] = 0;
try queue.append(gpa, start);
var head: usize = 0;
while (head < queue.items.len) {
const v = queue.items[head];
head += 1;
for (g.neighbors(v)) |nb| {
if (color[nb] == -1) {
color[nb] = 1 - color[v];
try queue.append(gpa, nb);
} else if (color[nb] == color[v]) {
return false; // edge between same-coloured -> not bipartite
}
}
}
queue.clearRetainingCapacity();
}
return true;
}
test "bipartite: even cycle yes, odd cycle no" {
const gpa = std.testing.allocator;
var even = try Graph.init(gpa, 4, false); // 0-1-2-3-0 square
defer even.deinit();
try even.addEdge(0, 1);
try even.addEdge(1, 2);
try even.addEdge(2, 3);
try even.addEdge(3, 0);
try std.testing.expect(try isBipartite(gpa, &even));
var odd = try Graph.init(gpa, 3, false); // triangle
defer odd.deinit();
try odd.addEdge(0, 1);
try odd.addEdge(1, 2);
try odd.addEdge(2, 0);
try std.testing.expect(!try isBipartite(gpa, &odd));
}
The even/odd cycle test is the classic mental model: any even-length cycle two-colours cleanly, any odd-length cycle (a triangle being the smallest) is doomed -- you go 0, 1, 0, 1 around the ring and the last vertex clashes with the first. clearRetainingCapacity reuses the queue's buffer between components in stead of freeing and re-allocating, a small allocator-honest touch.
Exercise 3 -- detect a cycle in a directed graph. Here the undirected "just ignore the parent" trick from last episode falls apart, and I promised you the real machinery: three colours. White means "not visited". Gray means "on the path I am currently exploring, still open". Black means "done, fully finished". A directed cycle exists the instant you follow an edge into a gray vertex -- that is a true back-edge, a loop closing on the path you are still standing on. Reaching a black vertex is fine (you have simply arrived at something you already finished by another route). I have written it iteratively, carrying an index per stack frame so we know which neighbour to visit next and, crucially, when a vertex's children are exhausted so we can paint it black:
fn hasCycleDirected(gpa: std.mem.Allocator, g: *const Graph) !bool {
const n = g.adj.items.len;
const Color = enum(u8) { white, gray, black };
const color = try gpa.alloc(Color, n);
defer gpa.free(color);
@memset(color, .white);
const Frame = struct { v: usize, idx: usize };
var stack: std.ArrayList(Frame) = .empty;
defer stack.deinit(gpa);
for (0..n) |start| {
if (color[start] != .white) continue;
try stack.append(gpa, .{ .v = start, .idx = 0 });
color[start] = .gray;
while (stack.items.len > 0) {
const top = &stack.items[stack.items.len - 1];
const nbs = g.neighbors(top.v);
if (top.idx < nbs.len) {
const nb = nbs[top.idx];
top.idx += 1;
switch (color[nb]) {
.gray => return true, // back-edge into the active path -> cycle
.white => {
color[nb] = .gray;
try stack.append(gpa, .{ .v = nb, .idx = 0 });
},
.black => {},
}
} else {
color[top.v] = .black; // fully explored
stack.items.len -= 1;
}
}
}
return false;
}
test "directed cycle detection: chain vs loop" {
const gpa = std.testing.allocator;
var chain = try Graph.init(gpa, 4, true); // 0->1->2->3
defer chain.deinit();
try chain.addEdge(0, 1);
try chain.addEdge(1, 2);
try chain.addEdge(2, 3);
try std.testing.expect(!try hasCycleDirected(gpa, &chain));
var loop = try Graph.init(gpa, 3, true); // 0->1->2->0
defer loop.deinit();
try loop.addEdge(0, 1);
try loop.addEdge(1, 2);
try loop.addEdge(2, 0);
try std.testing.expect(try hasCycleDirected(gpa, &loop));
}
That gray/black distinction is not just a cute trick -- it is the exact three-state bookkeeping that makes a topological sort possible, so keep it in the back of your mind. Debt paid ;-) Now, weights.
Picture a tiny road map. From your house (0) there is a direct road to the airport (3) that is long and slow -- weight 10. There is also a back route: house to the corner shop to the school to the airport, three short hops of weight 1 each, total 3. BFS, asked for the shortest path from house to airport, counts hops: the direct road is one hop, the back route is three. BFS declares the direct road the winner and reports a "distance" of 1. It is confidently, uselessly wrong, because the number it optimises (hop count) is not the number you care about (total weight).
The fix cannot be "just run BFS but add weights", because BFS's superpower came from a specific fact: with unit edges, the first time you reach a vertex you have reached it optimally, because you processed everything at distance 1 before anything at distance 2. With weights that ordering evaporates -- a vertex two cheap hops away can be closer than a vertex one expensive hop away, so the plain FIFO queue no longer hands vertices back in distance order. We need a queue that always gives us the closest not-yet-finalised vertex next, whatever order things were inserted. That data structure is a priority queue (a binary heap under the hood, episode-material in its own right), and Dijkstra's algorithm is precisely "BFS with a priority queue in stead of a plain one". That is the entire idea. Everything below is bookkeeping.
Our episode-118 Graph stored neighbours as bare usize vertex ids. A weighted graph has to store, for each edge, both the destination and its cost, so the neighbour lists become lists of a little Edge struct. Nothing else about the adjacency-list design changes -- it is the same allocator-honest, index-based shape we have used all series:
const Edge = struct { to: usize, weight: u32 };
const WeightedGraph = struct {
gpa: std.mem.Allocator,
adj: std.ArrayList(std.ArrayList(Edge)),
fn init(gpa: std.mem.Allocator, n: usize) !WeightedGraph {
var adj: std.ArrayList(std.ArrayList(Edge)) = .empty;
try adj.ensureTotalCapacity(gpa, n);
var i: usize = 0;
while (i < n) : (i += 1) adj.appendAssumeCapacity(.empty);
return .{ .gpa = gpa, .adj = adj };
}
fn deinit(self: *WeightedGraph) void {
for (self.adj.items) |*list| list.deinit(self.gpa);
self.adj.deinit(self.gpa);
}
fn addEdge(self: *WeightedGraph, from: usize, to: usize, weight: u32) !void {
try self.adj.items[from].append(self.gpa, .{ .to = to, .weight = weight });
try self.adj.items[to].append(self.gpa, .{ .to = from, .weight = weight });
}
fn neighbors(self: *const WeightedGraph, v: usize) []const Edge {
return self.adj.items[v].items;
}
};
I made addEdge undirected (it adds the edge in both directions) to keep the examples road-map-flavoured, and I chose u32 for weights on purpose: it forces the reader to think about the width, and it keeps dist sums in u64 comfortably clear of overflow even on big graphs. That width choice is a real design decision, not an accident -- Zig makes you name it, where a language with a single int would let you sleepwalk into a silent wraparound.
Here is the algorithm, and it is shorter than the explanation deserves. Keep a dist array seeded to "infinity" everywhere except the source (distance 0). Push the source into a min-priority-queue keyed on distance. Then repeatedly pop the closest pending vertex, and for each of its neighbours try to relax the edge: if going through the popped vertex reaches the neighbour more cheaply than any route found so far, record the cheaper distance and push the neighbour with its new key.
const INF: u64 = std.math.maxInt(u64);
const State = struct { dist: u64, vertex: usize };
fn stateLess(_: void, a: State, b: State) std.math.Order {
return std.math.order(a.dist, b.dist);
}
fn dijkstra(gpa: std.mem.Allocator, g: *const WeightedGraph, source: usize) ![]u64 {
const n = g.adj.items.len;
const dist = try gpa.alloc(u64, n);
errdefer gpa.free(dist);
@memset(dist, INF);
dist[source] = 0;
var pq: std.PriorityQueue(State, void, stateLess) = .empty;
defer pq.deinit(gpa);
try pq.push(gpa, .{ .dist = 0, .vertex = source });
while (pq.pop()) |cur| {
if (cur.dist > dist[cur.vertex]) continue; // stale, superseded entry
for (g.neighbors(cur.vertex)) |e| {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
try pq.push(gpa, .{ .dist = nd, .vertex = e.to });
}
}
}
return dist;
}
test "dijkstra finds the cheapest route, not the fewest hops" {
const gpa = std.testing.allocator;
var g = try WeightedGraph.init(gpa, 5);
defer g.deinit();
// 0 -> 1 (1) -> 2 (1) -> 3 (1): three cheap hops, total 3
// 0 -> 3 (10): one expensive hop
try g.addEdge(0, 1, 1);
try g.addEdge(1, 2, 1);
try g.addEdge(2, 3, 1);
try g.addEdge(0, 3, 10);
try g.addEdge(3, 4, 2);
const dist = try dijkstra(gpa, &g, 0);
defer gpa.free(dist);
try std.testing.expectEqual(@as(u64, 0), dist[0]);
try std.testing.expectEqual(@as(u64, 3), dist[3]); // 1+1+1 beats the direct 10
try std.testing.expectEqual(@as(u64, 5), dist[4]);
}
The test is the road map from earlier, and Dijkstra gets it right where BFS did not: dist[3] is 3 (the three-hop back route), not 10 (the direct road). Two details earn their keep. First, std.PriorityQueue(State, void, stateLess) -- the type takes the element, a context type (we do not need one, so void), and a comparison function that returns std.math.Order. Returning .lt when a should pop before b makes it a min-heap on distance, which is exactly what "give me the closest pending vertex" means. In Zig 0.16 the queue is unmanaged, so it starts as .empty and takes the allocator on each push and on deinit, the same shape as ArrayList -- one less hidden allocator to reason about.
Second, and this is the clever bit, the line if (cur.dist > dist[cur.vertex]) continue. A textbook Dijkstra wants a "decrease-key" operation: when you find a cheaper route to a vertex already sitting in the heap, you reach in and lower its key in place. Zig's PriorityQueue (like most) does not make that cheap, so we do the honest lazy thing instead -- we never modify a heap entry, we just push a new one with the better distance and leave the stale one to rot. When a stale entry eventually pops, its dist is larger than the finalised dist[vertex] we have since recorded, so we recognise it as garbage and continue past it. This "lazy deletion" costs a few extra heap slots but buys enormous simplicity, and it is what almost every real Dijkstra you will read actually does. Wowzers, such a small line for such a big idea ;-)
I could sprinkle a dozen hand-built graphs with hand-checked distances, but we learned a better discipline earlier in this arc: find a property that must hold for every possible input, then throw hundreds of random graphs at it. For shortest paths the perfect property is the triangle inequality on every edge. If dist[v] is truly the cheapest distance to v, then for any edge from u to v of weight w, it must be that dist[v] <= dist[u] + w. If that were ever false, it would mean there is a route to v (via u) cheaper than the "cheapest" one Dijkstra reported -- a contradiction. So we generate random weighted graphs and assert the inequality across every edge:
test "property: dijkstra output satisfies the edge relaxation invariant" {
const gpa = std.testing.allocator;
var prng = std.Random.DefaultPrng.init(0xBEEF);
const rand = prng.random();
var round: usize = 0;
while (round < 200) : (round += 1) {
const n = rand.intRangeAtMost(usize, 1, 20);
var g = try WeightedGraph.init(gpa, n);
defer g.deinit();
const m = rand.intRangeAtMost(usize, 0, 40);
for (0..m) |_| {
const a = rand.uintLessThan(usize, n);
const b = rand.uintLessThan(usize, n);
if (a == b) continue;
try g.addEdge(a, b, rand.intRangeAtMost(u32, 1, 100));
}
const src = rand.uintLessThan(usize, n);
const dist = try dijkstra(gpa, &g, src);
defer gpa.free(dist);
// for every edge u-v of weight w that is reachable: dist[v] <= dist[u] + w
for (0..n) |u| {
if (dist[u] == INF) continue;
for (g.neighbors(u)) |e| {
try std.testing.expect(dist[e.to] <= dist[u] + e.weight);
}
}
}
}
Two hundred random graphs, random weights, random sources, and the invariant holds every time -- and because it all runs on std.testing.allocator, any leaked heap or neighbour list fails the round too. A subtle bug like forgetting the stale-entry guard would not necessarily crash, but it would eventually relax an edge with wrong data and trip this inequality, which is exactly the kind of quiet correctness bug hand-written tests love to miss.
Notice the ugliness we have tolerated: dist[v] == INF (that is maxInt(u64)) is our stand-in for "no route exists". It works, but it is a magic sentinel -- a special value smuggled inside the normal range, the kind of thing that causes a bug the day someone has a legitimate distance near maxInt, or forgets the check. Zig gives us something better: the optional type ?u64, where null is the type-system's word for "nothing here". A thin wrapper turns the sentinel array into an honest optional array:
fn dijkstraOptional(gpa: std.mem.Allocator, g: *const WeightedGraph, source: usize) ![]?u64 {
const raw = try dijkstra(gpa, g, source);
defer gpa.free(raw);
const out = try gpa.alloc(?u64, raw.len);
for (raw, 0..) |d, i| out[i] = if (d == INF) null else d;
return out;
}
test "optional distances model unreachable as null" {
const gpa = std.testing.allocator;
var g = try WeightedGraph.init(gpa, 3);
defer g.deinit();
try g.addEdge(0, 1, 5);
// vertex 2 isolated
const dist = try dijkstraOptional(gpa, &g, 0);
defer gpa.free(dist);
try std.testing.expectEqual(@as(?u64, 0), dist[0]);
try std.testing.expectEqual(@as(?u64, 5), dist[1]);
try std.testing.expectEqual(@as(?u64, null), dist[2]);
}
Now a caller cannot accidentally treat "unreachable" as a huge-but-valid distance -- the compiler forces an if (dist[v]) |d| unwrap before the number is usable. This is the recurring Zig lesson of the whole series: prefer a type that makes the illegal state unrepresentable over a convention you have to remember. Having said that, inside the hot loop we still use the raw sentinel for speed (an ?u64 comparison is a hair heavier), and only convert at the boundary where humans read the result. That layering -- fast sentinel inside, honest optional at the edge -- is a very Zig way to have both.
Distances are half the story; usually you want the road, not just its length. Same trick as the BFS path finder last episode: carry a parent array, and every time relaxing an edge improves a neighbour's distance, record who improved it (parent[e.to] = cur.vertex). When Dijkstra finishes, walk parents backward from the target to the source and reverse:
fn dijkstraPath(gpa: std.mem.Allocator, g: *const WeightedGraph, source: usize, target: usize) !?[]usize {
const n = g.adj.items.len;
const dist = try gpa.alloc(u64, n);
defer gpa.free(dist);
@memset(dist, INF);
const parent = try gpa.alloc(i64, n);
defer gpa.free(parent);
@memset(parent, -1);
dist[source] = 0;
var pq: std.PriorityQueue(State, void, stateLess) = .empty;
defer pq.deinit(gpa);
try pq.push(gpa, .{ .dist = 0, .vertex = source });
while (pq.pop()) |cur| {
if (cur.dist > dist[cur.vertex]) continue;
for (g.neighbors(cur.vertex)) |e| {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
parent[e.to] = @intCast(cur.vertex);
try pq.push(gpa, .{ .dist = nd, .vertex = e.to });
}
}
}
if (dist[target] == INF) return null;
var path: std.ArrayList(usize) = .empty;
errdefer path.deinit(gpa);
var cur: i64 = @intCast(target);
while (cur != -1) : (cur = parent[@intCast(cur)]) {
try path.append(gpa, @intCast(cur));
}
std.mem.reverse(usize, path.items);
return try path.toOwnedSlice(gpa);
}
test "dijkstra path returns the cheapest route in order" {
const gpa = std.testing.allocator;
var g = try WeightedGraph.init(gpa, 5);
defer g.deinit();
try g.addEdge(0, 1, 1);
try g.addEdge(1, 3, 1);
try g.addEdge(0, 2, 1);
try g.addEdge(2, 3, 4);
const maybe = try dijkstraPath(gpa, &g, 0, 3);
try std.testing.expect(maybe != null);
const path = maybe.?;
defer gpa.free(path);
try std.testing.expectEqual(@as(usize, 0), path[0]);
try std.testing.expectEqual(@as(usize, 3), path[path.len - 1]);
try std.testing.expectEqual(@as(usize, 3), path.len); // 0 -> 1 -> 3
}
Even though 0 -> 2 -> 3 and 0 -> 1 -> 3 are both two hops, Dijkstra picks the 1 route (cost 2) over the 2 route (cost 1 + 4 = 5), and the parent walk faithfully reports 0, 1, 3. The return null on an unreachable target and the ?[]usize return type are the same honesty as before -- "no path" is a first-class outcome, not an exception. And toOwnedSlice hands the caller a right-sized slice, transferring ownership out of the ArrayList so the errdefer no longer applies once we return cleanly.
Dijkstra is uninformed -- it expands outward from the source in every direction equally, like a circular ripple, with no idea where the target is. If you are routing across a whole country to reach a city in the east, Dijkstra still cheerfully explores westward for a while. A* (pronounced "A-star") fixes that by giving the search a sense of direction: a heuristic function that estimates the remaining distance from any vertex to the target. Instead of always expanding the vertex with the smallest distance-so-far (g), A* expands the one with the smallest f = g + h, where h is the estimated distance still to go. Vertices that lie toward the goal get explored first; vertices pointing away wait.
The one rule that makes A* still correct is that the heuristic must be admissible -- it may never overestimate the true remaining distance. Underestimating is fine (Dijkstra itself is just A* with h = 0, the most pessimistic admissible heuristic there is). For a geometric graph the natural admissible heuristic is straight-line distance: the crow-flies gap between two points can never exceed the real road distance between them. So I attach a 2D coordinate to each vertex and use the (floored) Euclidean distance as h:
const Point = struct { x: f64, y: f64 };
fn heuristic(a: Point, b: Point) u64 {
const dx = a.x - b.x;
const dy = a.y - b.y;
return @intFromFloat(@floor(@sqrt(dx * dx + dy * dy)));
}
const AStarState = struct { f: u64, g: u64, vertex: usize };
fn aStarLess(_: void, a: AStarState, b: AStarState) std.math.Order {
return std.math.order(a.f, b.f);
}
fn astar(gpa: std.mem.Allocator, g: *const WeightedGraph, coords: []const Point, source: usize, target: usize) !?u64 {
const n = g.adj.items.len;
const best = try gpa.alloc(u64, n);
defer gpa.free(best);
@memset(best, INF);
best[source] = 0;
var pq: std.PriorityQueue(AStarState, void, aStarLess) = .empty;
defer pq.deinit(gpa);
try pq.push(gpa, .{ .f = heuristic(coords[source], coords[target]), .g = 0, .vertex = source });
while (pq.pop()) |cur| {
if (cur.vertex == target) return cur.g;
if (cur.g > best[cur.vertex]) continue;
for (g.neighbors(cur.vertex)) |e| {
const ng = cur.g + e.weight;
if (ng < best[e.to]) {
best[e.to] = ng;
const f = ng + heuristic(coords[e.to], coords[target]);
try pq.push(gpa, .{ .f = f, .g = ng, .vertex = e.to });
}
}
}
return null;
}
test "A* with an admissible heuristic agrees with dijkstra on cost" {
const gpa = std.testing.allocator;
// a small geometric graph: coords chosen so straight-line <= edge weight
const coords = [_]Point{
.{ .x = 0, .y = 0 },
.{ .x = 10, .y = 0 },
.{ .x = 20, .y = 0 },
.{ .x = 10, .y = 10 },
};
var g = try WeightedGraph.init(gpa, 4);
defer g.deinit();
try g.addEdge(0, 1, 10);
try g.addEdge(1, 2, 10);
try g.addEdge(0, 3, 15);
try g.addEdge(3, 2, 15);
const cost = try astar(gpa, &g, &coords, 0, 2);
const dist = try dijkstra(gpa, &g, 0);
defer gpa.free(dist);
try std.testing.expect(cost != null);
try std.testing.expectEqual(dist[2], cost.?); // both optimal: 20 via 0-1-2
}
The structure is almost identical to Dijkstra -- same relaxation, same lazy stale-entry guard, same min-heap. The only two differences are that the heap key is f = g + h in stead of just g, and that we can stop the instant we pop the target (because with an admissible heuristic, the first time the target comes off the heap its g is provably optimal). The test proves the payoff-preserving claim that matters: A* returns the same optimal cost as Dijkstra (20, via 0 -> 1 -> 2). What changes is not the answer but the work -- with a good heuristic A* touches far fewer vertices to get there. On a big map that is the difference between "instant" and "spinning", which is why every game pathfinder and every routing engine on the planet runs A*, not raw Dijkstra.
The heap-based Dijkstra we wrote runs in O((V + E) log V) -- every edge can trigger at most one heap push, and each heap operation is logarithmic. For sparse graphs (few edges per vertex, the common case: road networks, social graphs) that is excellent. But the heap has overhead, and on a dense graph -- one where nearly every pair of vertices is connected, so E approaches V squared -- there is a simpler variant that actually wins: skip the heap entirely and just linear-scan for the closest unfinished vertex each round. That is O(V squared), which beats O(E log V) precisely when E is already near V squared:
fn dijkstraDense(gpa: std.mem.Allocator, g: *const WeightedGraph, source: usize) ![]u64 {
const n = g.adj.items.len;
const dist = try gpa.alloc(u64, n);
errdefer gpa.free(dist);
@memset(dist, INF);
const done = try gpa.alloc(bool, n);
defer gpa.free(done);
@memset(done, false);
dist[source] = 0;
for (0..n) |_| {
// pick the unfinished vertex with the smallest tentative distance
var u: usize = n;
var best: u64 = INF;
for (0..n) |v| {
if (!done[v] and dist[v] < best) {
best = dist[v];
u = v;
}
}
if (u == n) break; // the rest is unreachable
done[u] = true;
for (g.neighbors(u)) |e| {
const nd = dist[u] + e.weight;
if (nd < dist[e.to]) dist[e.to] = nd;
}
}
return dist;
}
test "dense dijkstra matches the heap version" {
const gpa = std.testing.allocator;
var g = try WeightedGraph.init(gpa, 5);
defer g.deinit();
try g.addEdge(0, 1, 2);
try g.addEdge(1, 2, 3);
try g.addEdge(0, 2, 10);
try g.addEdge(2, 3, 1);
try g.addEdge(3, 4, 1);
const a = try dijkstra(gpa, &g, 0);
defer gpa.free(a);
const b = try dijkstraDense(gpa, &g, 0);
defer gpa.free(b);
try std.testing.expectEqualSlices(u64, a, b);
}
Same answers, different asymptotics -- the test pins that they agree, which is also a lovely example of using one implementation as a reference oracle for another. There is a further tier the theory books love, the Fibonacci-heap Dijkstra at O(E + V log V), but in practice its constant factors are so bad that a plain binary heap (or even this array scan) wins on real hardware almost always. The one hard limit worth burning in: Dijkstra assumes non-negative weights. The whole "once popped, a vertex is finalised" argument collapses the instant an edge can be negative, because a later, negative-weight detour could still lower a distance you already locked in. Negative edges need a different algorithm entirely -- a hint I will leave dangling.
In C, Dijkstra is the same loop but you bring your own binary heap -- typically a hand-rolled array with siftUp/siftDown helpers, or, honestly, a lot of production C just uses the O(V squared) array scan to dodge writing a heap at all. The dist array is a malloc'd block of int or long, "infinity" is INT_MAX, and there is no testing.allocator to catch the queue you forgot to free on the early-return-at-target path. The lazy-deletion trick is exactly as necessary in C, because decrease-key on a bare array heap is just as awkward there as here.
In Rust, you reach for std::collections::BinaryHeap, which is a max-heap, so everyone wraps their state in std::cmp::Reverse to flip it into the min-heap Dijkstra needs -- the moral equivalent of our stateLess returning .lt. Distances go in a Vec<u64>, unreachable is usually u64::MAX or an Option<u64> (Rust's Option is precisely our ?u64, and idiomatic Rust leans on it the same way we did). The borrow checker again nudges you toward the index-based graph we have used all series, because holding references into a graph while mutating a heap is exactly the aliasing it forbids. Line for line, idiomatic Rust Dijkstra and our Zig Dijkstra are near twins; Rust drops the heap for you, Zig makes the allocator explicit.
In Go, the priority queue is the famously verbose part -- you implement container/heap's five-method interface (Len, Less, Swap, Push, Pop) on a slice of your state type, which is a good chunk of boilerplate for what is one generic type in Zig. Distances are a []uint64 or a map[int]uint64 for sparse ids, the garbage collector spares you the defer deinit, and goroutines tempt people into parallel shortest paths, which -- like parallel BFS last episode -- is genuinely hard and rarely worth it below enormous graph sizes. Four languages, one algorithm, and in every one of them the priority queue is the beating heart and the non-negative-weight assumption is the same load-bearing footnote. Bam, jonguh ;-)
Return the route from A*, not just the cost. A* above returns only the total cost as a ?u64. Add a parent array to it exactly the way dijkstraPath does, and reconstruct the vertex sequence from source to target. Test that the returned path's edge weights sum to the cost A* reported -- a nice self-consistency check that catches a wrong parent link immediately.
Reject negative weights loudly. We said Dijkstra silently produces wrong answers on negative edges. Add a debug guard at the top of dijkstra that scans every edge and returns error.NegativeWeight if it finds one below zero (you will need to switch Edge.weight to a signed type, or accept an i64 weight, to make this expressible). Test that a graph with one negative edge triggers the error rather than returning garbage. This is the honest way to protect callers from an algorithm's preconditions.
Count the vertices each algorithm expands. Add a counter to both dijkstra and astar that increments every time a vertex is popped and not skipped as stale, and return it alongside the result. Build a graph shaped like a long grid, put the source at one corner and the target at the far corner, and print both counts. You should see A* expand dramatically fewer vertices than Dijkstra -- watching that number shrink as the heuristic sharpens is the single most convincing way to feel why A* matters.
We can now find the cheapest route through a weighted graph two ways, steer that search toward a goal, and rebuild the exact path -- a genuinely powerful toolbox. But look at the cracks we deliberately left open. Dijkstra flatly refuses negative edges, and pretending otherwise gives silent nonsense, so there is clearly a whole other shortest-path world for graphs where costs can go down as well as up. And there is an even more basic question we keep circling without answering: given a pile of edges arriving one at a time, are two vertices even in the same component yet -- a question you might ask millions of times as a graph is built, far too often to re-run a full traversal for each. That second question has a data structure so elegant and so fast it feels like cheating, and it is where we turn next. Plus, remember that gray/black cycle bookkeeping from the very top of today's episode? It is about to pay off in a big way ;-)
Bedankt voor het lezen, en tot de volgende keer!
@scipio