Shortest Path in an Unweighted Graph: Why BFS Just Works
Find the shortest path from a source to every node in an unweighted graph with BFS — the level-order intuition, JavaScript code, a full walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
When every edge costs the same, the shortest path is just the one with the fewest edges. That single observation is why you never need Dijkstra's heap or any weight bookkeeping for an unweighted graph — plain breadth-first search already visits nodes in exactly the right order.
The trick is why the order is right. BFS drains a queue in first-in-first-out order, and that FIFO discipline forces it to finish every node at distance d before it ever touches a node at distance d + 1. So the first time you reach a node, you've reached it by the shortest possible route. No node ever needs a correction.
Master this and you've got the backbone of Word Ladder, grid flood-fills, and any "minimum number of moves" puzzle.
The problem
Given an unweighted graph as an adjacency list graph (where graph[u] lists the neighbors of node u) and a source node src, return an array dist where dist[i] is the minimum number of edges on a path from src to node i. If a node is unreachable, its distance stays Infinity.
Input: graph = [[1, 3], [0, 2], [1, 3, 4], [0, 2, 4], [2, 3]]
src = 0
Output: [0, 1, 2, 1, 2]Read the input as five nodes in a ring-ish shape: node 0 connects to 1 and 3, node 2 connects to 1, 3, and 4, and so on. From node 0 you reach 1 and 3 in one hop, then 2 and 4 in two hops. Node 0 itself sits at distance 0.
The brute force baseline
Without the BFS insight, you might try every path. A depth-first search that explores each route and keeps the shortest one it finds looks reasonable:
function shortestDistanceDFS(graph, src) {
const n = graph.length;
const dist = new Array(n).fill(Infinity);
function dfs(node, depth) {
if (depth >= dist[node]) return; // no improvement, prune
dist[node] = depth;
for (const nbr of graph[node]) {
dfs(nbr, depth + 1);
}
}
dfs(src, 0);
return dist;
}This gets the right answer, but it wanders. DFS can dive deep down one branch, assign a node a large distance, then later discover a shorter route and rewrite it — re-exploring everything downstream. On a dense or highly connected graph the same nodes get revisited over and over, and the work explodes toward exponential in the worst case. You're paying to fix mistakes that BFS never makes in the first place.
The key insight: FIFO gives you distance order for free
BFS explores in waves. Start with the source alone (distance 0). Expand it to get every node one edge away (distance 1). Expand all of those to get everything two edges away (distance 2). Because a queue hands nodes back in the order they arrived, all the distance-1 nodes are dequeued before any distance-2 node — the wave at distance d is fully processed before the wave at d + 1 begins.
That ordering is the whole proof. The first time BFS discovers a node, it's arriving on the earliest wave that could possibly touch it, so the distance it records is the minimum. There is no shorter path lurking, and no future wave can beat it. This is why you check dist[neighbor] === Infinity: an infinite distance means "not yet discovered," and the current wave is guaranteed to be its shortest.
The optimal solution
function shortestDistance(graph, src) {
let n = graph.length;
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
let q = [src];
while (q.length) {
let curr = q.shift();
for (let neighbor of graph[curr]) {
if (dist[neighbor] == Infinity) {
dist[neighbor] = dist[curr] + 1;
q.push(neighbor);
}
}
}
return dist;
}Three moves carry the whole algorithm. Seed dist[src] = 0 and put the source in the queue. Dequeue the front node, and for each undiscovered neighbor, set its distance to dist[curr] + 1 and enqueue it. The dist[neighbor] == Infinity guard does double duty — it's both the "have I seen this node?" check and the "is this the shortest path?" guarantee, because on an unweighted graph those two questions have the same answer.
Note that a node's distance is written exactly once, at discovery, and never touched again. That's the payoff of processing waves in order.
Walkthrough
Tracing graph = [[1, 3], [0, 2], [1, 3, 4], [0, 2, 4], [2, 3]] from src = 0. Each row is one dequeue.
Dequeue curr | dist[curr] | Neighbors | Undiscovered → set | Queue after | dist after |
|---|---|---|---|---|---|
| — (seed) | 0 | — | dist[0] = 0 | [0] | [0, ∞, ∞, ∞, ∞] |
| 0 | 0 | 1, 3 | 1→1, 3→1 | [1, 3] | [0, 1, ∞, 1, ∞] |
| 1 | 1 | 0, 2 | 2→2 (0 seen) | [3, 2] | [0, 1, 2, 1, ∞] |
| 3 | 1 | 0, 2, 4 | 4→2 (0,2 seen) | [2, 4] | [0, 1, 2, 1, 2] |
| 2 | 2 | 1, 3, 4 | none (all seen) | [4] | [0, 1, 2, 1, 2] |
| 4 | 2 | 2, 3 | none (all seen) | [] | [0, 1, 2, 1, 2] |
Watch the waves fall out cleanly: node 0 (distance 0), then 1 and 3 (distance 1), then 2 and 4 (distance 2). By the time node 2 is dequeued, every node is already discovered, so the last two rows only confirm the answer. The queue empties and BFS returns [0, 1, 2, 1, 2].
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(V + E) | Each vertex is enqueued/dequeued once; each edge is inspected once from its owner |
| Space | O(V) | The dist array and the queue each hold at most V entries |
The Infinity guard is what pins this to linear time: a node enters the queue exactly once, so the inner loop runs a total of E times across the whole traversal, not E times per node. One practical footnote — q.shift() on a JavaScript array is O(V) because it re-indexes, so a very large graph is faster with a head pointer or a deque, but the asymptotic edge/vertex counts stay the same.
Common mistakes
- Using
q.pop()instead ofq.shift(). Popping from the back turns the queue into a stack, and you've silently written a DFS. The FIFO order is the entire reason distances come out minimal — break it and node distances stop being shortest paths. - Setting the distance when you dequeue instead of when you enqueue. If you wait until a node is dequeued to mark it discovered, the same node can be enqueued multiple times through different edges before it's ever processed, inflating both the queue and your distances.
- Forgetting unreachable nodes. Initialize
disttoInfinity, not0or-1by accident. Nodes in a disconnected component are never enqueued, and theirInfinityis the correct, meaningful answer. - Reaching for weights that aren't there. If every edge is unit-cost, Dijkstra's priority queue is pure overhead. BFS is simpler and faster (O(V + E) vs O(E log V)) and gives the identical result.
Where this pattern shows up next
The "BFS finds the fewest-edges path" idea is the seed for a whole family of problems:
- Word Ladder — treat each word as a node and one-letter edits as edges; the shortest transformation is a BFS distance.
- Breadth First Search (BFS) — the traversal primitive underneath everything here, in its purest form.
- Reconstruct Itinerary — a graph-traversal cousin where edge ordering, not distance, drives the walk.
- Swim in Rising Water — what happens when edges do carry cost and plain BFS is no longer enough.
You can also step through the BFS shortest-path visualizer to watch the wave layers expand and the distance array fill in one dequeue at a time.
FAQ
Why does BFS find the shortest path but DFS doesn't?
BFS processes nodes in strict distance order because its queue is FIFO: every node at distance d is dequeued before any node at distance d + 1. So the first time a node is reached, it's on the shortest possible wave. DFS follows one branch as deep as it can before backtracking, so it can assign a node a long distance first and only later stumble onto a shorter route — which forces corrections and re-exploration. Without weights, BFS never needs a correction.
Does this work if the graph has weighted edges?
No. BFS assumes every edge costs the same one unit, so "fewest edges" equals "shortest path." The moment edges carry different weights, a path with more edges can be cheaper, and BFS's wave order no longer matches cost order. For non-negative weights you need Dijkstra's algorithm with a priority queue; for possible negative weights, Bellman-Ford. BFS is the special-case fast path for unit weights only.
Why check dist[neighbor] === Infinity instead of a separate visited set?
The distance array already carries the visited information. A value of Infinity means "never reached," and any finite value means "reached, and on an unweighted graph that distance is final." So the single array does two jobs — it prevents re-enqueuing a node and it records the answer — with no second data structure. It works precisely because BFS discovers every node at its shortest distance the first time, so once a value is finite there's no reason to revisit it.
How do I handle nodes that can't be reached from the source?
Initialize the whole dist array to Infinity before you start. BFS only ever enqueues nodes it can reach through edges from the source, so anything in a disconnected component is simply never touched and keeps its Infinity. That's the intended, correct output: Infinity is the answer for "no path exists." In the disconnected test case [[1], [0, 2], [1], [4], [3]] starting at node 0, nodes 3 and 4 stay at Infinity because no edge bridges the two components.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.