Shortest path in undirected graph with unit weights

Hard

BFS gives distances directly

Problem

Return shortest distances from a source in an unweighted graph.

In simple words

With all weights equal to 1, a plain BFS from the source finds every shortest distance.

The idea

When every edge costs the same, BFS reaches vertices in non-decreasing distance order, so the first time it touches a vertex is the shortest path. Dijkstra would work but is unnecessary overhead.

The trick

First visit is final — no relaxation needed.
Store a parent per vertex to reconstruct the path.
O(V + E) versus Dijkstra's O(E log V).

←→stepspaceplay

minute0

fresh6

1/6

Optimal

timeO(rows·cols)spaceO(rows·cols)

All sources start at minute 0.

1// enqueue all rotten cells; BFS by layers,2// converting fresh neighbors, counting minutes.3while (q.length && fresh > 0) {4  minutes++;5  for (let n = q.length; n > 0; n--) spread(q.shift());6}7return fresh === 0 ? minutes : -1;

Input

grid: 3 × 3

Memory

minute: 0
fresh: 6

Output

minute: 0
fresh: 6
answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n=6, edges=[[0,1],[0,3],[3,4],[4,5],[5,1],[1,2]], src=0
Output:: [0, 1, 2, 1, 2, 2]
Explanation:: Every edge counts as 1, so BFS gives distances.

Example 2

Input:: n=3, edges=[[0,1],[1,2]], src=0
Output:: [0, 1, 2]
Explanation:: 0,1,2.

Example 3

Input:: n=2, edges=[], src=0
Output:: [0, -1]
Explanation:: Node 1 unreachable → -1.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.