Shortest Path in Undirected Graph with Unit Weights

Given an undirected graph with V vertices (0 .. V-1) and edge list edges where every edge has weight 1, return an array dist with the shortest distance from source vertex 0 to every vertex (the fewest edges), or -1 if unreachable.

Hints

· Stuck? Reveal one nudge at a time.

All edges cost the same, so the fewest-edges path is the shortest path.

BFS visits vertices in increasing distance order — use it from the source.

The level at which BFS first reaches a vertex is its distance.

Common doubts

Dijkstra's heap orders by weighted distance; with unit weights BFS's queue already yields vertices in distance order, so a plain queue suffices.

BFS reaches a vertex first via a shortest path, so its initial distance is final — re-visits would only be longer.

They keep the initial -1 since BFS never reaches them.

Interview follow-ups

· What an interviewer asks next.

Use 0-1 BFS with a deque — push 0-weight neighbours to the front, 1-weight to the back.

Then you need Dijkstra with a priority queue.

Fun facts

BFS is Dijkstra's algorithm specialised to unit weights — the heap collapses into a queue.
This is the engine behind word ladder and other 'fewest steps' puzzles.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 5, edges = [[0,1],[0,2],[1,3],[3,4]]
Output: [0, 1, 1, 2, 3]
BFS levels from vertex 0.

Example 2

Input: V = 4, edges = [[0,1],[2,3]]
Output: [0, 1, -1, -1]
Vertices 2 and 3 aren't reachable from 0.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - all edges have weight 1 - no self-loops or duplicate edges

When every edge costs the same, BFS is the shortest-path algorithm: it visits vertices in order of increasing distance, so the level at which a vertex is first reached is its shortest distance. Start a BFS from source 0 with dist[0] = 0; each unvisited neighbour gets dist[u] + 1. Unreached vertices keep -1. O(V + E) — no priority queue, because with unit weights BFS's queue already dequeues in distance order.

(The brute alternative — Bellman-Ford-style relaxation of all edges V-1 times — gives the same answer at O(V·E), but is overkill when a plain BFS suffices.)

Prerequisites

Before you start

· Concepts used directly in the solution.

BFS = shortest path. on an unweighted graph, first-reach distance is minimal.

Distance array. initialise -1, set on first visit.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“All edge weights equal?”

Yes — weight 1, so BFS applies.

“Source and unreachable?”

Source is 0; unreachable vertices report -1.

The ideal opening — say it like this

With unit weights, BFS from the source gives shortest distances — the level a vertex is first reached at.

It's O(V+E); no heap needed because the queue already processes vertices in distance order.

Understand the problem

Worked example — V = 5, edges [[0,1],[0,2],[1,3],[3,4]]

level 0: 0
level 1: 1, 2
level 2: 3
level 3: 4
dist = [0, 1, 1, 2, 3]

Key observations

1Aha

BFS level = distance

Unit weights make ring number equal shortest distance.

2Aha

First visit is shortest

Mark distance when a vertex is first dequeued-neighbour.

3Aha

No heap needed

The queue already yields vertices in distance order.

Brute force vs optimal

	Edge relaxation	BFS
Idea	relax all edges V-1 times	expand rings from the source
Time	O(V·E)	O(V+E)
Needs unit weights

Both give the same distances; BFS is the right tool for unit weights. Full code is in the Approaches selector below.

Summary

Key takeaway

With unit weights, BFS from the source computes all shortest distances in O(V+E): the level a vertex is first reached is its distance. Unreached ⇒ -1.

dist[0]=0; BFS; neighbour's dist = dist[u]+1 on first visit