Algorithms from zero
Unweighted shortest path with BFS
In the last lesson you learned that BFS explores a graph level by level using a queue, and that the first time it reaches a vertex, it reaches it by the fewest edges. That last sentence is a complete shortest-path algorithm hiding inside a traversal. If you also remember which vertex you came from, you do not just learn the distance—you can rebuild the actual route, step by step. This lesson turns plain BFS into a shortest-path machine for unweighted graphs: keep a dist[] array and a parent[] map as you go, then walk parent[] backward to print a concrete path. One warning up front: this trick works only when every edge counts the same. Put weights on the edges (cost 1 here, cost 7 there) and BFS quietly gives the wrong answer—that is where Dijkstra takes over next lesson.
After this lesson you can run BFS while filling a dist[] array (distance in edges from the source to every reachable vertex) and a parent[] map (the vertex you arrived from). You understand why this is correct: BFS dequeues vertices in non-decreasing order of distance, so the first time you reach a vertex is along a path with the fewest edges. You can reconstruct a concrete shortest path by walking parent[] backward from the target to the source and reversing the list. You know the boundary of the technique: it is valid only for unweighted (or unit-weight) graphs; weighted edges break it and require Dijkstra. You can extend BFS to multiple sources at once (multi-source BFS) by seeding the queue with several starts at distance 0. You know the cost stays O(V + E) time and O(V) space. Next lesson: Dijkstra’s algorithm for weighted graphs.
The shortest path question
In an unweighted graph, the length of a path is simply the number of edges on it. The shortest path from a source to a target is the path with the fewest edges. We want two things for every reachable vertex: its distance from the source, and a concrete route to it.
Why plain BFS already solves it
BFS processes vertices in non-decreasing order of distance: it empties level 0 (the source, distance 0), then all of level 1 (distance 1), then level 2, and so on. Because of this order, the very first time BFS reaches a vertex, it has reached it by the fewest possible edges. There is no shorter route waiting to be found later, because any later route is discovered at an equal or greater distance. So the moment we enqueue a vertex is the moment we learn its true shortest distance.
Two arrays to record the answer
We add two pieces of bookkeeping to ordinary BFS:
- dist[v] — the distance (number of edges) from the source to v. Set
dist[u] = dist[v] + 1when we first reach u from v. - parent[u] — the vertex we arrived from when we first reached u. This is the breadcrumb that lets us walk back to the source.
Both are filled at the same instant: when we first see an unvisited neighbor u while processing v.
Example graph
An undirected, unweighted graph with 6 vertices:
Adjacency list:
A: [B, C]
B: [A, D, E]
C: [A, F]
D: [B]
E: [B, F]
F: [C, E]
Visual:
A
/ \
B C
/ \ \
D E---FThere are two routes from A to F: A-C-F (2 edges) and A-B-E-F (3 edges). BFS must find the 2-edge one.
BFS trace with dist and parent (source = A)
Mark a vertex when you enqueue it (the mark is “has a dist value yet”).
Init: queue = [A] dist[A]=0, parent[A]=null
Pop A. neighbors B, C (both new)
dist[B]=1 parent[B]=A enqueue B
dist[C]=1 parent[C]=A enqueue C
queue = [B, C]
Pop B. neighbors A(seen), D(new), E(new)
dist[D]=2 parent[D]=B enqueue D
dist[E]=2 parent[E]=B enqueue E
queue = [C, D, E]
Pop C. neighbors A(seen), F(new)
dist[F]=2 parent[F]=C enqueue F
queue = [D, E, F]
Pop D. neighbors B(seen) queue = [E, F]
Pop E. neighbors B(seen), F(seen) queue = [F]
Pop F. neighbors C(seen), E(seen) queue = []
Done.
dist: A=0 B=1 C=1 D=2 E=2 F=2
parent: A=null B=A C=A D=B E=B F=CNote F got parent=C (not E), because C was dequeued before E, so F was first reached from C. That is exactly the shorter route.
Reconstructing the concrete path A -> F
Walk parent[] backward from the target, then reverse:
start at F path = [F] parent[F]=C
go to C path = [F, C] parent[C]=A
go to A path = [F, C, A] parent[A]=null -> stop
reverse path = [A, C, F]The reconstructed shortest path is A -> C -> F, length 2 edges, matching dist[F]=2.
The weighted-graph trap
Suppose the same shape, but edge A-C costs 10 while A-B, B-E, E-F each cost 1. Now the cheapest route is A-B-E-F (cost 3), but BFS still reports A-C-F as “shortest” because it counts edges, not cost. BFS is blind to weights. The fix is a different algorithm—Dijkstra—which always expands the cheapest-cost frontier next. BFS shortest paths are correct only when every edge has the same weight (which we can treat as 1).
BFS that fills dist[] and parent[]
1
function bfsShortestPath(source, adj) {
2
const dist = {}; // distance in edges from source
3
const parent = {}; // vertex we arrived from
4
const queue = [source];
5
6
dist[source] = 0; // source is 0 edges from itself
7
parent[source] = null; // source has no parent
8
9
while (queue.length > 0) {
10
const v = queue.shift(); // dequeue (FIFO)
11
for (const u of adj[v]) {
12
if (!(u in dist)) { // first time we reach u
13
dist[u] = dist[v] + 1; // one edge farther than v
14
parent[u] = v; // remember the breadcrumb
15
queue.push(u); // enqueue (mark-on-enqueue)
16
}
17
}
18
}
19
20
return { dist, parent };
21
}
- L2 dist doubles as the visited marker: 'u in dist' means u was already reached.
- L3 parent[u] records the predecessor on a shortest path to u.
- L6 Source sits at distance 0 from itself.
- L7 Source has no predecessor; null stops the backward walk later.
- L10 shift() removes from the front of the queue: FIFO, the key to distance order.
- L12 Check 'in dist', not a separate set, so we never reach the same vertex twice.
- L13 First arrival = shortest distance, so dist[v]+1 is final for u.
- L14 Set parent at the same instant we set dist.
- L15 Mark on enqueue (by giving it a dist) so it is never enqueued again.
Reconstructing a concrete path
1
function reconstructPath(target, parent) {
2
const path = [];
3
let cur = target;
4
while (cur !== null && cur !== undefined) {
5
path.push(cur); // collect from target back to source
6
cur = parent[cur]; // step to the predecessor
7
}
8
path.reverse(); // flip so it reads source -> target
9
return path;
10
}
- L4 null means we reached the source; undefined means target is unreachable.
- L5 We collect vertices in reverse order: target first.
- L6 Follow the breadcrumb chain one hop toward the source.
- L8 Reverse to get the natural source-to-target order.
Running it on the example graph
1
adj = { A:[B,C], B:[A,D,E], C:[A,F], D:[B], E:[B,F], F:[C,E] };
2
dist[A]=0; parent[A]=null;
3
queue = [A];
Time complexity: O(V + E)
This is BFS with two cheap extra writes per vertex, so the cost is unchanged. Each vertex is enqueued exactly once (the u in dist check guarantees it), and when dequeued we scan all its incident edges. Setting dist[u] and parent[u] is O(1) each. Summed over the whole run: V enqueues + E edge scans = O(V + E).
Path reconstruction is O(L), where L is the path length, which is at most V vertices. That is dominated by the BFS itself, so the total stays O(V + E).
Space complexity: O(V)
The dist[] map holds up to V entries: O(V). The parent[] map holds up to V entries: O(V). The queue holds at most V vertices at once: O(V). Total: O(V).
Why the first arrival is the shortest
BFS dequeues in non-decreasing distance order. Concretely, every vertex enqueued from a vertex at distance d gets distance d+1, and all distance-d vertices are dequeued before any distance-(d+1) vertex. So when a vertex is first reached, no shorter unexplored route can exist—any other route is found at the same distance or later.
Distances grow monotonically across the queue:
queue: [ d=1, d=1, d=2, d=2, d=2 ] (never [d=2, d=1])Why weights break it
A --1-- B --1-- E --1-- F total cost 3
A --10- C --1-- F total cost 11
BFS counts edges, not cost:
A->C->F = 2 edges -> BFS calls this "shortest"
A->B->E->F = 3 edges
But by COST, A->B->E->F (3) beats A->C->F (11).BFS reports the fewest-edges path, which is wrong when edges have different weights. Use Dijkstra for weighted graphs.
Why does the first time BFS reaches a vertex correspond to its shortest distance from the source?
What is the role of the parent[] (predecessor) map in BFS shortest paths?
You reconstruct a path by following parent[] backward from the target. In what order do the vertices come out, and what fixes it?
A graph has edges with different positive weights and you want the minimum-cost path. Is plain BFS correct?
Multi-source BFS finds, for each vertex, the distance to the nearest of several sources. How do you set it up?
In the lesson graph (A:[B,C], B:[A,D,E], C:[A,F], D:[B], E:[B,F], F:[C,E]), what is dist[F], the shortest number of edges from A to F?
Why this works
Why dist[] doubles as the visited set. We never need a separate visited structure. The test u in dist is true exactly when u has already been reached and enqueued. Reusing dist[] keeps the bookkeeping to one place: a vertex is “visited” the instant it gets a distance, which is also the instant we set its parent. Fewer arrays, fewer chances to forget to update one of them.
Common mistake
Setting dist or parent on a later visit. A vertex can be a neighbor of several others, so you may encounter it again after it is already in dist[]. Do not overwrite dist[u] or parent[u] on those later encounters—the first assignment is the shortest one, and a later edge only ever offers an equal or longer route. Guard every update with if (!(u in dist)).
Edge cases
Unreachable targets. If the target is in a different component from the source, BFS never assigns it a distance, so dist[target] is undefined and parent[target] is undefined too. The reconstruction loop stops immediately (cur is undefined), returning a list that does not start at the source. Check target in dist first, and report “no path” if it is missing.
More practice
Grid shortest paths. A maze or grid is a graph in disguise: each open cell is a vertex, and adjacent open cells (up/down/left/right) are connected by unit-weight edges. BFS from the start cell gives the fewest-step path to the exit, and parent[] reconstructs the route. This is the everyday use of unweighted-shortest-path BFS in games and pathfinding on uniform terrain.
Explain how BFS computes unweighted shortest paths, what dist[] and parent[] are for, how to reconstruct a concrete path, and when this technique stops being correct.
BFS is already a shortest-path algorithm for unweighted graphs: it dequeues vertices in non-decreasing order of distance, so the first time it reaches a vertex is along a path with the fewest edges.
Bookkeeping: keep dist[v] (edges from the source) and parent[v] (the vertex you arrived from). Set both at the moment you first enqueue v—and never overwrite them later.
Reconstruct a path: walk parent[] backward from the target to the source, then reverse. The length equals dist[target].
Extension: multi-source BFS seeds the queue with several sources at distance 0 and finds each vertex’s distance to its nearest source in one pass.
Time: O(V + E). Space: O(V).
The boundary: this works only when every edge counts the same. Differing edge weights break BFS, because it minimizes edge count, not cost. Next lesson: Dijkstra’s algorithm—shortest paths on weighted graphs.