python 38 lines · 9 steps

Breadth-first search and shortest paths in Python

A queue-driven traversal that visits a graph level by level, then extends to track the shortest path between two nodes.

Explained by highlit
Intermediate graph-traversal bfs queue shortest-path algorithms
1from collections import deque
2 
3 
4def bfs(graph, start):
5 """Traverse a graph breadth-first, returning nodes in visit order."""
6 visited = {start}
7 order = []
8 queue = deque([start])
9 
10 while queue:
11 node = queue.popleft()
12 order.append(node)
13 for neighbor in graph[node]:
14 if neighbor not in visited:
15 visited.add(neighbor)
16 queue.append(neighbor)
17 
18 return order
19 
20 
21def shortest_path(graph, start, goal):
22 """Find the shortest path between two nodes using BFS."""
23 if start == goal:
24 return [start]
25 
26 visited = {start}
27 queue = deque([(start, [start])])
28 
29 while queue:
30 node, path = queue.popleft()
31 for neighbor in graph[node]:
32 if neighbor == goal:
33 return path + [neighbor]
34 if neighbor not in visited:
35 visited.add(neighbor)
36 queue.append((neighbor, path + [neighbor]))
37 
38 return None
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1BFS explores a graph in waves, so the first time it reaches a node is along a shortest edge-count path.
  2. 2Marking nodes visited at enqueue time — not dequeue time — prevents the same node from being queued multiple times.
  3. 3Carrying the path alongside each queued node turns plain BFS into a shortest-path finder.

Related explainers

python 
from fastapi import FastAPI, WebSocket, WebSocketDisconnect
 
app = FastAPI()
 

Building a WebSocket chat with FastAPI

websockets broadcast connection-management
Intermediate 9 steps
python 
import time
import uuid
 
from django.utils.deprecation import MiddlewareMixin

Attaching per-request context in Django

middleware request lifecycle multi-tenancy
Intermediate 7 steps
python 
import random
from typing import Iterator, List
 
 

How reservoir sampling picks k items

reservoir-sampling streaming randomness
Intermediate 5 steps
python 
import secrets
 
from django.contrib.auth import authenticate, login
from django.core.cache import cache

Two-factor login with OTP in Django

two-factor-auth one-time-passwords caching
Intermediate 9 steps
python 
import re
from functools import total_ordering
from typing import Optional
 

Parsing and comparing semantic versions

regex operator-overloading sorting
Intermediate 7 steps
python 
from typing import Any, Sequence, Mapping
 
 
def render_markdown_table(

Rendering an aligned Markdown table in Python

string formatting data transformation closures
Intermediate 8 steps

Share this explainer

Here's the card — post it anywhere.

Breadth-first search and shortest paths in Python — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code