BFS Shortest Path in an Unweighted Graph

Find the minimum number of edges (and optionally the actual route) between two vertices in an unweighted graph using BFS.

Language Selection

Choose your preferred programming language

Showing: Python

BFS Shortest Path in an Unweighted Graph

Problem Statement

You are given an undirected, unweighted graph with:

V vertices labeled 0..V-1
an edge list edges, where each edge is a pair [u, v]
two vertices src and dest

Return:

the length of the shortest path from src to dest measured in number of edges, and
the actual shortest path as a list of vertices (inclusive), e.g. [src, ..., dest].

If dest is unreachable from src, return length -1 and an empty path.

Examples

Example 1

V = 6
edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]]
src = 0, dest = 5

Shortest path length is 4 (edges), and one shortest path is:

0 -> 1 -> 3 -> 4 -> 5

Output:

length: 4
path: [0, 1, 3, 4, 5]

Example 2 (unreachable)

V = 4
edges = [[0,1],[2,3]]
src = 0, dest = 3

Output:

length: -1
path: []

Example 3 (src == dest)

V = 3
edges = [[0,1],[1,2]]
src = 2, dest = 2

Output:

length: 0
path: [2]

Notes:
This is the canonical “shortest path in an unweighted graph” interview pattern.
BFS is the authoritative/standard technique because it explores vertices in increasing number-of-edges layers.

Intuition — what insight unlocks the solution?

In an unweighted graph, every edge has the same “cost” (1 hop). BFS explores the graph in waves:

First all nodes at distance 1
Then all nodes at distance 2
Then distance 3, etc.

So the first time BFS reaches a node, it must have used the fewest edges possible to get there. That’s exactly what “shortest path” means in an unweighted graph.

This problem follows the Graph Traversal (BFS) pattern.

Approach

Approach 1: Brute Force (DFS enumerate paths) — not recommended

A naive idea is to try all possible paths from src to dest (DFS/backtracking) and keep the minimum length.

Why it’s bad:

The number of simple paths can be exponential.
Easy to get wrong with cycles (you must track visited per path).

This approach will time out on non-trivial graphs.

Approach 2 (Optimal): BFS + Parent Reconstruction

We’ll use:

adj: adjacency list
dist[v]: shortest distance (#edges) from src to v (initialize to -1 meaning unvisited)
parent[v]: previous node on the shortest path to v (initialize to -1)
a queue for BFS

Step-by-step

Build an adjacency list from edges.
Initialize dist[src] = 0, push src into the queue.
While the queue is not empty:
- pop u
- for each neighbor v of u:
  - if dist[v] == -1 (unvisited):
    - set dist[v] = dist[u] + 1
    - set parent[v] = u
    - push v
If dist[dest] == -1, it’s unreachable → return (-1, []).
Otherwise reconstruct the path by walking backward from dest using parent[] until -1, then reverse.

Why marking visited when enqueuing matters We set dist[v] immediately when we enqueue v. This ensures:

each node enters the queue at most once
the first recorded parent is guaranteed to produce a shortest path

Solution

Python:

from collections import deque
from typing import List, Tuple


def bfs_shortest_path_unweighted(V: int, edges: List[List[int]], src: int, dest: int) -> Tuple[int, List[int]]:
    """Returns (distance_in_edges, path_vertices). If unreachable: (-1, [])."""
    if V <= 0:
        return -1, []
    if src < 0 or src >= V or dest < 0 or dest >= V:
        return -1, []

    # Build adjacency list
    adj = [[] for _ in range(V)]
    for u, v in edges:
        # Ignore malformed edges safely
        if 0 <= u < V and 0 <= v < V:
            adj[u].append(v)
            adj[v].append(u)

    dist = [-1] * V
    parent = [-1] * V

    q = deque([src])
    dist[src] = 0

    while q:
        u = q.popleft()
        if u == dest:
            break  # optional early exit

        for v in adj[u]:
            if dist[v] == -1:  # unvisited
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)

    if dist[dest] == -1:
        return -1, []

    # Reconstruct path from dest back to src using parent pointers
    path = []
    cur = dest
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()

    return dist[dest], path


if __name__ == "__main__":
    V = 6
    edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5]]
    print(bfs_shortest_path_unweighted(V, edges, 0, 5))  # (4, [0, 1, 3, 4, 5])

Java:

import java.util.*;

public class Solution {

    // Returns int[]{distance, ...path...} encoded as a Result object for clarity.
    static class Result {
        int distance;          // number of edges; -1 if unreachable
        List<Integer> path;    // empty if unreachable
        Result(int distance, List<Integer> path) {
            this.distance = distance;
            this.path = path;
        }
    }

    public static Result bfsShortestPathUnweighted(int V, int[][] edges, int src, int dest) {
        if (V <= 0 || src < 0 || src >= V || dest < 0 || dest >= V) {
            return new Result(-1, new ArrayList<>());
        }

        // Build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            if (e == null || e.length != 2) continue;
            int u = e[0], v = e[1];
            if (0 <= u && u < V && 0 <= v && v < V) {
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
        }

        int[] dist = new int[V];
        int[] parent = new int[V];
        Arrays.fill(dist, -1);
        Arrays.fill(parent, -1);

        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(src);
        dist[src] = 0;

        while (!q.isEmpty()) {
            int u = q.poll();
            if (u == dest) break; // optional early exit

            for (int v : adj.get(u)) {
                if (dist[v] == -1) { // unvisited
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    q.add(v);
                }
            }
        }

        if (dist[dest] == -1) {
            return new Result(-1, new ArrayList<>());
        }

        // Reconstruct path
        LinkedList<Integer> path = new LinkedList<>();
        int cur = dest;
        while (cur != -1) {
            path.addFirst(cur);
            cur = parent[cur];
        }

        return new Result(dist[dest], path);
    }

    public static void main(String[] args) {
        int V = 6;
        int[][] edges = {{0,1},{0,2},{1,3},{2,3},{3,4},{4,5}};
        Result r = bfsShortestPathUnweighted(V, edges, 0, 5);
        System.out.println("distance=" + r.distance + ", path=" + r.path);
    }
}

Go:

package main

import (
	"container/list"
	"fmt"
)

type Result struct {
	Distance int
	Path     []int
}

func bfsShortestPathUnweighted(V int, edges [][]int, src, dest int) Result {
	if V <= 0 || src < 0 || src >= V || dest < 0 || dest >= V {
		return Result{Distance: -1, Path: []int{}}
	}

	// Build adjacency list
	adj := make([][]int, V)
	for _, e := range edges {
		if len(e) != 2 {
			continue
		}
		u, v := e[0], e[1]
		if 0 <= u && u < V && 0 <= v && v < V {
			adj[u] = append(adj[u], v)
			adj[v] = append(adj[v], u)
		}
	}

	dist := make([]int, V)
	parent := make([]int, V)
	for i := 0; i < V; i++ {
		dist[i] = -1
		parent[i] = -1
	}

	q := list.New()
	q.PushBack(src)
	dist[src] = 0

	for q.Len() > 0 {
		front := q.Front()
		u := front.Value.(int)
		q.Remove(front)

		if u == dest {
			break // optional early exit
		}

		for _, v := range adj[u] {
			if dist[v] == -1 { // unvisited
				dist[v] = dist[u] + 1
				parent[v] = u
				q.PushBack(v)
			}
		}
	}

	if dist[dest] == -1 {
		return Result{Distance: -1, Path: []int{}}
	}

	// Reconstruct path
	path := make([]int, 0)
	for cur := dest; cur != -1; cur = parent[cur] {
		path = append(path, cur)
	}
	// reverse
	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}

	return Result{Distance: dist[dest], Path: path}
}

func main() {
	V := 6
	edges := [][]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}}
	res := bfsShortestPathUnweighted(V, edges, 0, 5)
	fmt.Println(res.Distance, res.Path)
}

JavaScript:

/**
 * Returns { distance: number, path: number[] }
 * distance is number of edges; -1 if unreachable.
 */
function bfsShortestPathUnweighted(V, edges, src, dest) {
  if (V <= 0 || src < 0 || src >= V || dest < 0 || dest >= V) {
    return { distance: -1, path: [] };
  }

  // Build adjacency list
  const adj = Array.from({ length: V }, () => []);
  for (const e of edges) {
    if (!e || e.length !== 2) continue;
    const [u, v] = e;
    if (u >= 0 && u < V && v >= 0 && v < V) {
      adj[u].push(v);
      adj[v].push(u);
    }
  }

  const dist = Array(V).fill(-1);
  const parent = Array(V).fill(-1);

  // Simple queue with head index (avoids O(n) shift)
  const queue = [src];
  let head = 0;
  dist[src] = 0;

  while (head < queue.length) {
    const u = queue[head++];
    if (u === dest) break; // optional early exit

    for (const v of adj[u]) {
      if (dist[v] === -1) {
        dist[v] = dist[u] + 1;
        parent[v] = u;
        queue.push(v);
      }
    }
  }

  if (dist[dest] === -1) {
    return { distance: -1, path: [] };
  }

  // Reconstruct path
  const path = [];
  for (let cur = dest; cur !== -1; cur = parent[cur]) {
    path.push(cur);
  }
  path.reverse();

  return { distance: dist[dest], path };
}

// Demo
const V = 6;
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5]];
console.log(bfsShortestPathUnweighted(V, edges, 0, 5));

C#:

using System;
using System.Collections.Generic;

public class Solution
{
    public class Result
    {
        public int Distance;         // number of edges; -1 if unreachable
        public List<int> Path;       // empty if unreachable
        public Result(int distance, List<int> path)
        {
            Distance = distance;
            Path = path;
        }
    }

    public static Result BfsShortestPathUnweighted(int V, int[][] edges, int src, int dest)
    {
        if (V <= 0 || src < 0 || src >= V || dest < 0 || dest >= V)
            return new Result(-1, new List<int>());

        // Build adjacency list
        var adj = new List<int>[V];
        for (int i = 0; i < V; i++) adj[i] = new List<int>();

        foreach (var e in edges)
        {
            if (e == null || e.Length != 2) continue;
            int u = e[0], v = e[1];
            if (0 <= u && u < V && 0 <= v && v < V)
            {
                adj[u].Add(v);
                adj[v].Add(u);
            }
        }

        int[] dist = new int[V];
        int[] parent = new int[V];
        Array.Fill(dist, -1);
        Array.Fill(parent, -1);

        var q = new Queue<int>();
        q.Enqueue(src);
        dist[src] = 0;

        while (q.Count > 0)
        {
            int u = q.Dequeue();
            if (u == dest) break; // optional early exit

            foreach (int v in adj[u])
            {
                if (dist[v] == -1)
                {
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    q.Enqueue(v);
                }
            }
        }

        if (dist[dest] == -1)
            return new Result(-1, new List<int>());

        // Reconstruct path
        var path = new List<int>();
        for (int cur = dest; cur != -1; cur = parent[cur])
            path.Add(cur);
        path.Reverse();

        return new Result(dist[dest], path);
    }

    public static void Main()
    {
        int V = 6;
        int[][] edges = new int[][]
        {
            new int[] {0, 1}, new int[] {0, 2}, new int[] {1, 3},
            new int[] {2, 3}, new int[] {3, 4}, new int[] {4, 5}
        };

        var res = BfsShortestPathUnweighted(V, edges, 0, 5);
        Console.WriteLine($"distance={res.Distance}, path=[{string.Join(",", res.Path)}]");
    }
}

Complexity Analysis

Let V be the number of vertices and E be the number of edges.

Time: O(V + E) because BFS enqueues/dequeues each vertex at most once (O(V)), and across the whole run it iterates over each adjacency list entry once (total O(E) for directed, O(2E) for undirected, still O(E)).
Space: O(V + E) because the adjacency list stores all edges (O(V + E)), and dist, parent, and the queue each store up to O(V) items.

Common Mistakes

Using DFS and hoping to get the shortest path: DFS does not explore by increasing hop-count, so it won’t reliably find shortest paths.
Marking visited too late (when dequeuing instead of when enqueuing): leads to repeated enqueues and can break parent reconstruction.
Off-by-one in “path length”:
- This page defines length as number of edges.
- Some platforms output number of nodes in the path (e.g., len(path)), which differs by 1.
Not storing parent[]: you can compute distance, but you cannot reconstruct the path.
Using an adjacency matrix for large graphs: it makes traversal O(V^2) and often times out.

Multi-source BFS (shortest distance to any source)
Grid shortest path with obstacles (still BFS)
0–1 BFS (edges with weights 0 or 1)
Dijkstra’s algorithm (general positive weights)
Bidirectional BFS (optimize single-pair shortest path on large graphs)

Language Selection

BFS Shortest Path in an Unweighted Graph

Problem Statement

Examples

Intuition — what insight unlocks the solution?

Approach

Approach 1: Brute Force (DFS enumerate paths) — not recommended

Approach 2 (Optimal): BFS + Parent Reconstruction

Solution

Complexity Analysis

Common Mistakes

Related / Follow-up Problems

Share this