Graphs · question

Question 9 of 60

How do you find the shortest path in an unweighted graph?

beginner

Re-explain

Plain breadth-first search solves this directly, with no fancier algorithm needed. Because BFS reaches vertices in order of hop count, the first time it touches a vertex is along a fewest-edge path. Every edge counts as one step, so fewest edges means shortest.

To recover the actual route, record where you came from. When you first visit a neighbor, store the vertex you arrived from as its parent. Once you reach the target, walk parent pointers backward to rebuild the path, then reverse it.

parent[neighbor] = current; // set on first visit

The whole thing runs in O(V + E) time and space.

The one catch is that this only holds when every edge has the same cost. Add real weights and fewest edges no longer means cheapest, so BFS gives wrong distances.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Graphs One question at a time. Answer out loud, get graded, see what you missed.

See it - interactive diagram

BFS parent pointers rebuild a shortest path

const parent = {A: null};

const queue = ['A'];

while (queue.length) {

const cur = queue.shift();

for (let n of graph[cur])

if (!(n in parent)) {

parent[n] = cur;

queue.push(n);

}

let path = [], v = 'E';

while (v !== null) {

path.push(v);

v = parent[v];

}

path.reverse();

graphsource A, target E

Queuevertices waiting their turn

parentvertex = where we came from

Anull

pathbuilt backward, then reversed

empty

1step

We want a shortest path from A to E. A waits in the queue with no parent. Each vertex waits, comes out, then is done.

1 / 10

BFS gives each vertex one parent on its first visit. Walk the parents from the target back to the source, then reverse the list. That is a shortest path.

Other questions have diagrams like this too. Sign in to ask for one where it's missing - it's free.

Create a free account

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

Why mark a vertex visited when you enqueue it rather than when you dequeue it? Marking on dequeue lets a vertex sit in the queue many times, which bloats it, and a later discovery can overwrite its parent with a longer route.
Why does this stop working once edges have weights, and what do you use instead? Show a case where the fewest-hop path costs more. Then name Dijkstra for non-negative weights and Bellman-Ford when weights can be negative.
How would you get each cell's distance to its nearest exit in a grid maze? Seed one BFS with every exit at distance 0. Don't run a separate BFS from each cell or from each exit.
If every edge weighs either 0 or 1, can you still avoid a priority queue? 0-1 BFS uses a deque. It pushes 0-weight neighbors to the front and 1-weight ones to the back, and it stays O(V + E).
The graph is huge and you need one source-to-target path. How do you shrink the search? Run BFS from both ends until the frontiers meet. This needs a known target and a way to follow edges backward.

What you can say

I'd use plain breadth-first search, because in an unweighted graph every edge counts as one step, so the path with the fewest edges is the shortest.
BFS reaches vertices in order of hop count, so the first time it touches a vertex, it got there along a fewest-edge path.
To get the route itself, I record a parent for each vertex when I first discover it, meaning the vertex I arrived from.
Once I reach the target, I walk the parent pointers back to the source and reverse that list to get the path.
The whole thing is O(V + E) in time and space.
The catch is that this only holds when every edge costs the same. With real weights, fewest edges no longer means cheapest, so BFS would give wrong distances.

Weak answers to avoid

Reaches for Dijkstra by default Dijkstra works, but it adds a heap and a log factor for nothing. When every edge costs the same, plain BFS is already correct and runs in O(V + E).
Uses DFS to find the shortest path DFS finds a path, but its first route to the target can be much longer than needed. BFS's hop-count order is what guarantees the first visit is shortest.
Returns the distance but can't rebuild the path Interviewers usually want the route too. Set parent[neighbor] = current on first visit, then walk back from the target and reverse.
Never states the equal-weight condition Saying BFS finds shortest paths in general is wrong. It holds only when every edge costs the same, because with real weights fewest edges isn't cheapest.

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Graphs cheatsheet.

← Back to all Graphs questions

Pro · $10/mo

51 of 60 Graphs answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →