DSA Tracker

Visualize

Shortest Path in Unweighted Graph

BFS: with every edge worth 1 step, the first visit to a node IS its shortest distance

time O(V + E)space O(V + E)

When every edge costs the same, distance from the source is just how many BFS layers deep a node sits — so plain level-by-level BFS, not Dijkstra, already finds the shortest path. Track one distance per node (unknown until first discovered) and one parent pointer to rebuild the actual route afterward. The moment the destination is pulled off the queue, its distance is final and the answer is that number; nothing later in the queue can ever produce a shorter route to it.

Details

Animated on: n = 6, edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], source = 0, destination = 5 — shortest distance?

Problem:Shortest Path in Unweighted GraphMedium

BFS: with every edge worth 1 step, the first visit to a node IS its shortest distance

step 1 / 15

Undirected graph, unit edge weights

6 nodes, every edge worth 1 step. Find node 0's shortest distance to node 5. With every edge the same length, BFS visits nodes in strict order of distance from the source, so the first time 5 comes out of the queue, that distance is final.

Pseudocode
1FUNCTION shortestPath(n, edges, source, dest):
2  BUILD adjacency list FROM edges
3  FOR c FROM 0 TO n - 1
4    dist[c] <- -1
5  dist[source] <- 0
6  queue <- [source]
7  WHILE queue NOT EMPTY
8    u <- REMOVE FIRST FROM queue
9    IF u = dest
10      RETURN dist[u]
11    FOR EACH v IN adjacency[u]
12      IF dist[v] = -1
13        dist[v] <- dist[u] + 1
14        APPEND v TO queue
15  RETURN dist[dest]

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. 6 nodes, every edge worth 1 step. Find node 0's shortest distance to node 5. With every edge the same length, BFS visits nodes in strict order of distance from the source, so the first time 5 comes out of the queue, that distance is final.
  2. Every distance starts unknown except the source itself, which is 0 steps from itself. Queue holds just 0.
  3. Dequeue 0 (dist 0). Look at its neighbours 1, 2 for any that have never been reached.
  4. 1 gets dist 1, 2 gets dist 1 — first time seeing them through 0, so they're queued with parent 0.
  5. Dequeue 1 (dist 1). Look at its neighbours 0, 3 for any that have never been reached.
  6. 3 gets dist 2 — first time seeing it through 1, so it's queued with parent 1.
  7. Dequeue 2 (dist 1). Look at its neighbours 0, 3 for any that have never been reached.
  8. Every neighbour of 2 already has a distance, so nothing changes and nothing new is queued.
  9. Dequeue 3 (dist 2). Look at its neighbours 1, 2, 4 for any that have never been reached.
  10. 4 gets dist 3 — first time seeing it through 3, so it's queued with parent 3.
  11. Dequeue 4 (dist 3). Look at its neighbours 3, 5 for any that have never been reached.
  12. 5 gets dist 4 — first time seeing it through 4, so it's queued with parent 4.
  13. Dequeue 5 (dist 4). Look at its neighbours 4 for any that have never been reached.
  14. 5 IS the destination, and BFS only reaches it once, at its true shortest distance. No point scanning the rest of the queue — stop here.
  15. Walking parent pointers back from 5 to 0 gives 0 -> 1 -> 3 -> 4 -> 5, 4 edges long. RETURN dist[5] = 4.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Shortest Path in Unweighted Graph in the editorAll Graph problemsBack to roadmap