Pattern visualizer

Shortest Path in Unweighted Graph

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. Animated on: n = 6, edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], source = 0, destination = 5 — shortest distance?.

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)step 1 / 15

Undirected graph, unit edge weights

line 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.

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap