10.2 Finding Shortest Paths with BFS

Use BFS when every edge has the same cost. In that setting, the shortest path is the path with the fewest edges, and BFS finds it by exploring the graph one distance layer at a time.

This recipe focuses on the standard single-source BFS form: given a source vertex, compute the shortest distance to every reachable vertex.

Problem

Given an unweighted graph and a source vertex s, compute the minimum number of edges from s to every other vertex.

For example, in this graph:

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

Starting from vertex 0, the shortest distances are:

0: 0
1: 1
2: 1
3: 2
4: 2
5: 3

Solution

Use a queue. Initialize the source distance to 0, then push the source into the queue. When a vertex is removed from the queue, inspect each neighbor. If the neighbor has not been visited, set its distance and enqueue it.

package main

import "fmt"

func shortestPathsBFS(graph [][]int, source int) []int {
	n := len(graph)

	dist := make([]int, n)
	for i := range dist {
		dist[i] = -1
	}

	queue := make([]int, 0, n)
	queue = append(queue, source)
	dist[source] = 0

	head := 0

	for head < len(queue) {
		v := queue[head]
		head++

		for _, next := range graph[v] {
			if dist[next] != -1 {
				continue
			}

			dist[next] = dist[v] + 1
			queue = append(queue, next)
		}
	}

	return dist
}

func main() {
	graph := [][]int{
		{1, 2},
		{0, 3, 4},
		{0, 4},
		{1},
		{1, 2, 5},
		{4},
	}

	fmt.Println(shortestPathsBFS(graph, 0))
}

Output:

[0 1 1 2 2 3]

The value -1 means the vertex is unreachable from the source.

Why This Works

BFS processes vertices in increasing distance order.

At the beginning, the queue contains only the source:

distance 0: 0

After processing vertex 0, the queue receives its undiscovered neighbors:

distance 1: 1, 2

After processing those vertices, the next layer is discovered:

distance 2: 3, 4

Then:

distance 3: 5

Because every edge has cost 1, no path reaching a vertex later can be shorter than the first path that discovered it. The first distance assigned to a vertex is therefore final.

The core invariant is:

When a vertex is dequeued, its distance is the shortest possible distance from the source.

This is the reason BFS solves shortest paths in unweighted graphs, while ordinary DFS does not.

Using a Head Index Instead of Slicing

A common Go mistake is to implement a queue like this:

v := queue[0]
queue = queue[1:]

That works for small examples, but it can retain references to the old backing array and may create avoidable memory pressure.

A better pattern is to keep a head index:

head := 0

for head < len(queue) {
	v := queue[head]
	head++
}

This keeps queue operations simple and avoids repeated slicing.

Path Reconstruction

Distances answer “how far?” To answer “which path?”, store the predecessor of each vertex.

func shortestPathsWithParent(graph [][]int, source int) ([]int, []int) {
	n := len(graph)

	dist := make([]int, n)
	parent := make([]int, n)

	for i := range dist {
		dist[i] = -1
		parent[i] = -1
	}

	queue := make([]int, 0, n)
	queue = append(queue, source)
	dist[source] = 0

	head := 0

	for head < len(queue) {
		v := queue[head]
		head++

		for _, next := range graph[v] {
			if dist[next] != -1 {
				continue
			}

			dist[next] = dist[v] + 1
			parent[next] = v
			queue = append(queue, next)
		}
	}

	return dist, parent
}

To rebuild the path from source to target, walk backward through parent.

func buildPath(parent []int, target int) []int {
	if target < 0 || target >= len(parent) {
		return nil
	}

	path := []int{}

	for target != -1 {
		path = append(path, target)
		target = parent[target]
	}

	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}

	return path
}

Example:

func main() {
	graph := [][]int{
		{1, 2},
		{0, 3, 4},
		{0, 4},
		{1},
		{1, 2, 5},
		{4},
	}

	dist, parent := shortestPathsWithParent(graph, 0)

	fmt.Println(dist)
	fmt.Println(buildPath(parent, 5))
}

Output:

[0 1 1 2 2 3]
[0 1 4 5]

Depending on adjacency order, another valid shortest path may be found. For this graph, [0 2 4 5] is also shortest.

Complexity

For an adjacency-list graph, BFS visits each vertex once and scans each edge once in a directed graph. In an undirected graph, each edge appears in two adjacency lists, but the bound remains linear.

Operation	Cost
Initialize arrays	O(V)
BFS traversal	O(V + E)
Distance lookup	O(1)
Reconstruct one path	O(path length)
Extra memory	O(V)

Here V is the number of vertices and E is the number of edges.

Common Mistakes

Do not mark a vertex as visited only when it is dequeued. Mark it when it is enqueued. Otherwise, the same vertex may enter the queue many times through different parents.

Do not use BFS for weighted shortest paths. If edges have different weights, BFS no longer expands vertices in increasing path cost. Use Dijkstra for nonnegative weights, Bellman-Ford for negative weights, or another algorithm appropriate to the graph.

Do not assume the predecessor tree is unique. BFS returns one shortest-path tree, not all shortest paths.

Do not use recursion for BFS. BFS is naturally queue-based. Recursive DFS has different traversal semantics and does not preserve shortest-path layers.

Takeaway

BFS is the correct tool for shortest paths in unweighted graphs. The queue preserves distance-layer order, and the first time a vertex is discovered, its distance is final. Add a parent array when you need the actual route, not just the distance.