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.

Basic Implementation

basic.f90

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

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, matching the lesson spec.

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