Graphs

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.

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

Basic Implementation

basic.sql
Replay: real traced execution (multi-file project)
.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;

  1. edge ← (empty)

    2.headers off3CREATE TABLE edge(u INTEGER, v INTEGER);4INSERT INTO edge(u, v) VALUES
    values this step(empty)edge

  2. edge ← [(1,2),(1,3),(2,4),(3,4),(4,5),(5,6)]

    3CREATE TABLE edge(u INTEGER, v INTEGER);4INSERT INTO edge(u, v) VALUES5  (1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 6);
    values this step[(1,2),(1,3),(2,4),(3,4),(4,5),(5,6)]edge

  3. distance from 1 ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}

    15),16bfs(node, depth, path) AS (17  SELECT 1, 0, '1'
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}distance from 1

  4. shortest path ← [1, 2, 4, 5, 6] distance 4

    22)23SELECT '[' || REPLACE(path, ',', ', ') || '] distance ' || depth24FROM bfs
    values this step[1, 2, 4, 5, 6] distance 4shortest path

  5. BFS path ← 1 -> 2 (1 edge, cost 10), cheaper weighted path ← 1 -> 3 -> 2 (2 edges, cost 2)

    22)23SELECT '[' || REPLACE(path, ',', ', ') || '] distance ' || depth24FROM bfs
    values this step1 -> 2 (1 edge, cost 10)BFS path1 -> 3 -> 2 (2 edges, cost 2)cheaper weighted pathuse Dijkstra with a priority queueweighted algorithm1->2 weight 10, 1->3 weight 1, 3->2 weight 1edge weights

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. It also contrasts that unweighted result with a weighted graph where Dijkstra with a priority queue is required.