Shortest Paths with Breadth-First Search

The previous graph note discussed minimum spanning trees. Shortest paths answer a different question: instead of connecting the whole graph as cheaply as possible, we want the cheapest route from one place to another.

Imagine cities A through E, with A as a production center. Finding the shortest delivery route from A to every other city is a single-source shortest-path problem. Finding the shortest route for every pair of cities is an all-pairs shortest-path problem.

Different algorithms apply to different graph types:

BFS for an unweighted graph

Breadth-first search visits a graph layer by layer. An unweighted graph can also be viewed as a weighted graph in which every edge has weight 1, so the first time BFS reaches a vertex it has found a minimum-edge path from the source.

For the example graph, starting from vertex 2:

• first layer: vertices 1 and 6;
• second layer: vertices 5, 3, and 7;
• third layer: vertices 4 and 8.

Implementation

void BFS_MIN_Distance(Graph G, int source) {
    for (int i = 0; i < G.vexnum; ++i) {
        d[i] = INFINITY; // unreachable until discovered
        path[i] = -1;    // no predecessor yet
        visited[i] = FALSE;
    }

    d[source] = 0;
    visited[source] = TRUE;
    EnQueue(Q, source);

    while (!isEmpty(Q)) {
        int u;
        DeQueue(Q, u);

        for (int w = FirstNeighbor(G, u);
             w >= 0;
             w = NextNeighbor(G, u, w)) {
            if (!visited[w]) {
                d[w] = d[u] + 1;
                path[w] = u;
                visited[w] = TRUE;
                EnQueue(Q, w);
            }
        }
    }
}

The three important pieces of state are:

• visited[v]: whether v has already been discovered;
• d[v]: the minimum number of edges from the source to v;
• path[v]: the predecessor of v on the discovered shortest path.

The queue preserves layer order.

Walking through the example

Initialize all vertices as unvisited, all distances as unreachable, and all predecessors as -1. Then mark source vertex 2, set d[2] = 0, and enqueue it.

Dequeue vertex 2

Its unvisited neighbors are 1 and 6:

queue: 1, 6
d[1] = 1, path[1] = 2
d[6] = 1, path[6] = 2

Dequeue vertex 1

Vertex 2 is already visited. Discover vertex 5:

queue: 6, 5
d[5] = 2, path[5] = 1

Dequeue vertex 6

Discover vertices 3 and 7:

queue: 5, 3, 7
d[3] = 2, path[3] = 6
d[7] = 2, path[7] = 6

Continue by queue order

Vertex 5 adds nothing new. Vertex 3 discovers vertex 4, and vertex 7 discovers vertex 8. The final arrays are:

The queue is now empty, so traversal is complete.

Reconstructing a path

For vertex 4:

d[4] = 3
path[4] = 3
path[3] = 6
path[6] = 2

Following predecessors backward gives 4 ← 3 ← 6 ← 2. Reverse that sequence to obtain the shortest route:

2 → 6 → 3 → 4

Its length is three edges, matching d[4].

BFS solves this cleanly because every edge has equal cost. Weighted graphs require algorithms such as Dijkstra or Floyd, which are separate topics.