Shortest path in an unweighted graph

If every edge has weight 1, the shortest path from a source s to any vertex v is found by BFS layers: the first time we reach v, we have used the minimum number of edges. Store dist[v] = number of edges from s; initialize dist[s]=0 and relax neighbors when first discovered.

1) Relation to BFS

Use the same queue-based BFS as BFS using queue. When dequeuing u and seeing neighbor v unvisited, set dist[v] = dist[u] + 1 (and optionally record parent for path reconstruction).

2) Algorithm sketch

3) Example in C

Same undirected graph as the BFS page: vertices 0–4, edges 0–1, 0–2, 1–3, 2–4. Source s = 0.

#include <stdio.h>

#define V 5
#define MAXE 16
#define INF -1

static int adj[V][MAXE];
static int deg[V];
static int dist[V];

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

int main(void) {
    int q[V * V], front = 0, rear = 0;
    int s = 0;

    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 3);
    add_edge(2, 4);

    for (int i = 0; i < V; i++) dist[i] = INF;
    dist[s] = 0;
    q[rear++] = s;

    while (front < rear) {
        int u = q[front++];
        for (int i = 0; i < deg[u]; i++) {
            int v = adj[u][i];
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q[rear++] = v;
            }
        }
    }

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

Graph structure (same as previous)

Edges:

• 0-1
• 0-2
• 1-3
• 2-4

Visual graph:

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

Initial state

BFS execution step-by-step

Queue evolution

Distance array updates

BFS levels (layers from source)

Visual level graph:

Level 2          Level 1          Level 0          Level 1          Level 2
  3   <<<<<<<<<   1   <<<<<<<<<   0   >>>>>>>>>   2   >>>>>>>>>   4
(dist=2)          (dist=1)          (dist=0)          (dist=1)          (dist=2)

Final output

Shortest edge-count from 0:
  dist[0] = 0
  dist[1] = 1
  dist[2] = 1
  dist[3] = 2
  dist[4] = 2

Key differences from previous BFS code

Time Complexity: O(V + E) = O(5 + 4) = O(9)
Space Complexity: O(V) = O(5) for queue + distance array

4) Weighted graphs

If edges have different positive weights, use Dijkstra (non-negative weights) or Bellman–Ford (general edge weights). BFS distance is only for unit edges.