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 (space-separated) with 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.f90
Replay: real traced execution (multi-file project)
program graph_shortest_path
    implicit none
    integer, parameter :: N = 6
    integer :: adj(N, 3) = 0
    integer :: adj_len(N)
    integer :: dist(N)
    integer :: parent(N)
    integer :: queue(N)
    integer :: path(N)
    integer :: head, tail, src, dst, v, i, nb, node, path_count

    adj_len = [2, 2, 2, 3, 2, 1]
    adj(1, 1:2) = [2, 3]
    adj(2, 1:2) = [1, 4]
    adj(3, 1:2) = [1, 4]
    adj(4, 1:3) = [2, 3, 5]
    adj(5, 1:2) = [4, 6]
    adj(6, 1:1) = [5]

    src = 1
    dst = 6
    dist = -1
    parent = 0
    dist(src) = 0
    queue(1) = src
    head = 1
    tail = 1

    do while (head <= tail)
        v = queue(head)
        head = head + 1
        do i = 1, adj_len(v)
            nb = adj(v, i)
            if (dist(nb) == -1) then
                dist(nb) = dist(v) + 1
                parent(nb) = v
                tail = tail + 1
                queue(tail) = nb
            end if
        end do
    end do

    path_count = 0
    node = dst
    do while (node /= 0)
        path_count = path_count + 1
        path(path_count) = node
        node = parent(node)
    end do

    print '(*(I0,1X))', (path(i), i = path_count, 1, -1)
    print '(I0)', dist(dst)
end program graph_shortest_path

  1. dist ← {1: 0}

    23parent = 024dist(src) = 025queue(1) = src
    values this step{1: 0}dist

  2. parent ← {1: null}

    22dist = -123parent = 024dist(src) = 0
    values this step{1: null}parent

  3. dist ← {1: 0, 2: 1, 3: 1}, parent ← {1: null, 2: 1, 3: 1}, queue ← [2, 3]

    29do while (head <= tail)30    v = queue(head)31    head = head + 1
    values this step{1: 0, 2: 1, 3: 1}dist{1: null, 2: 1, 3: 1}parent[2, 3]queue1dequeue

  4. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    29do while (head <= tail)30    v = queue(head)31    head = head + 1
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[3, 4]queue2dequeue

  5. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    29do while (head <= tail)30    v = queue(head)31    head = head + 1
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[4]queue3dequeue

  6. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4}

    29do while (head <= tail)30    v = queue(head)31    head = head + 1
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4}parent[5]queue4dequeue

  7. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    29do while (head <= tail)30    v = queue(head)31    head = head + 1
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[6]queue5dequeue

  8. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    29do while (head <= tail)30    v = queue(head)31    head = head + 1
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[]queue6dequeue

  9. path ← [1, 2, 4, 5, 6]

    44node = dst45do while (node /= 0)46    path_count = path_count + 1
    values this step[1, 2, 4, 5, 6]path{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent

  10. stdout ← 1 2 4 5 6

    51print '(*(I0,1X))', (path(i), i = path_count, 1, -1)52print '(I0)', dist(dst)
    values this step1 2 4 5 6stdout[1, 2, 4, 5, 6]path

  11. stdout ← 4

    51    print '(*(I0,1X))', (path(i), i = path_count, 1, -1)52    print '(I0)', dist(dst)53end program graph_shortest_path
    values this step4stdout4dist(6)

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

    51    print '(*(I0,1X))', (path(i), i = path_count, 1, -1)52    print '(I0)', dist(dst)53end program graph_shortest_path
    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

  • Fortran: dist initialised to -1 doubles as the visited check, parent records predecessors (0 marks the source), and a ring of indices over queue gives FIFO order.
  • 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.