Shortest path (unweighted)

When every edge counts as one step, the shortest path from a source s to v is measured in edge count (also called hop count or unweighted distance). A single run of BFS from s discovers vertices in nondecreasing distance from s; the first time v is dequeued, dist[v] equals that minimum number of edges. This fails for graphs with different edge costs—you need shortest-path algorithms for weighted edges.

1) Why BFS?

The BFS queue processes the frontier of vertices at distance k before any vertex at distance k + 1 is expanded. So the first assignment dist[v] = dist[u] + 1 uses the smallest possible dist[u] among paths that can reach v in one more step—exactly the shortest edge-count distance in an unweighted graph.

2) Algorithm

• Initialize dist[u] = -1 (or another sentinel) for all u; set dist[s] = 0 and enqueue s.
• While the queue is nonempty: dequeue u. For each neighbor v with dist[v] < 0, set dist[v] = dist[u] + 1, optionally parent[v] = u, enqueue v.
• If dist[v] stays -1, vertex v is not reachable from s in an undirected component sense (or not reachable following arc directions in a directed graph).

3) Example graph

Undirected graph on vertices 0 … 4 (same structure as BFS on graphs): edges 0–1, 0–2, 1–3, 2–4. Source s = 0.

        3
        |
        1
        |
    0 --- 2 --- 4

4) C — BFS distances (adjacency lists)

#include <stdio.h>

#define V 5
#define MAXD 8          /* max neighbors per vertex for this demo */
#define INF -1           /* not discovered / unreachable */

static int adj[V][MAXD];   /* undirected: store neighbor ids */
static int deg[V];
static int dist[V];        /* hop count from source */
static int parent[V];      /* tree edge for one shortest path */

static void edge(int a, int b) {
    adj[a][deg[a]++] = b;
    adj[b][deg[b]++] = a;
}

int main(void) {
    /* same 5-vertex shape as the BFS lesson */
    edge(0, 1);
    edge(0, 2);
    edge(1, 3);
    edge(2, 4);

    int s = 0;
    int q[V * V], qh = 0, qt = 0;   /* simple FIFO queue */

    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        parent[i] = INF;
    }
    dist[s] = 0;
    parent[s] = s;   /* or -1; only used to stop path walk */
    q[qt++] = s;

    while (qh < qt) {
        int u = q[qh++];   /* expand frontier at smallest dist */
        for (int k = 0; k < deg[u]; k++) {
            int v = adj[u][k];
            if (dist[v] != INF) continue;   /* already shortest hops */
            dist[v] = dist[u] + 1;   /* each edge costs 1 */
            parent[v] = u;
            q[qt++] = v;
        }
    }

    printf("dist from %d:\n", s);
    for (int i = 0; i < V; i++)
        printf("  dist[%d] = %d\n", i, dist[i]);

    int t = 4;
    printf("path %d -> %d (one shortest): ", s, t);
    if (dist[t] < 0) {
        printf("unreachable\n");
    } else {
        int stack[V], sp = 0;
        for (int x = t; x != s; x = parent[x])
            stack[sp++] = x;   /* reverse order for printing */
        printf("%d", s);
        while (sp > 0) printf(" -> %d", stack[--sp]);
        printf("\n");
    }
    return 0;
}

5) Complexity

Each vertex enters the queue at most once; each edge is examined when its endpoint is processed: O(V + E) time with adjacency lists, O(V²) with an adjacency matrix if you scan full rows. Extra space O(V) for dist, queue, and parent.

6) Trace — source 0

FIFO queue; neighbors processed in insertion order from edge() calls.

Shortest path from 0 to 4 uses two edges (e.g. 0 → 2 → 4). From 0 to 3: two edges (0 → 1 → 3).