Shortest Path (Unweighted, via BFS)

BFS explores a graph layer by layer, so the first time it reaches a vertex is along a shortest path. Track distance and predecessor while exploring, then walk predecessors back from the target to reconstruct the route.

Algorithm

On the canonical graph from graph-adjacency-list, the shortest path from 1 to 6 is [1, 2, 4, 5, 6] distance 4. The path is rebuilt from the predecessor of each vertex: 6 -> 5 -> 4 -> 2 -> 1, reversed.

Basic Implementation

basic.sql

.mode list
.headers off
CREATE TABLE edge(u INTEGER, v INTEGER);
INSERT INTO edge(u, v) VALUES
  (1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 6);

-- BFS over simple paths: each row extends a path by one unvisited neighbour,
-- so depth equals distance. The shortest path to 6 is the min-depth row,
-- ties broken by the lexicographically smallest path.
WITH RECURSIVE
adj(u, v, seq) AS (
  SELECT u, v, rowid * 2 - 1 FROM edge
  UNION ALL
  SELECT v, u, rowid * 2 FROM edge
),
bfs(node, depth, path) AS (
  SELECT 1, 0, '1'
  UNION
  SELECT a.v, b.depth + 1, b.path || ',' || a.v
  FROM bfs b JOIN adj a ON a.u = b.node
  WHERE instr(',' || b.path || ',', ',' || a.v || ',') = 0
)
SELECT '[' || REPLACE(path, ',', ', ') || '] distance ' || depth
FROM bfs
WHERE node = 6
ORDER BY depth, path
LIMIT 1;

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

SQL: a recursive CTE extends simple paths one neighbour at a time, so depth equals distance; the shortest path to 6 is the min-depth row.
The replay shows the distances and predecessors filling in, then the reconstructed path, matching the lesson spec.

layers equal distance BFS order equals distance in an unweighted graph.