Shortest Paths
Fewest steps with BFS.
How many handshakes away is Ana from Fay? Breadth first search can tell us, and show the exact chain of people. Because it explores in rings, the first time it reaches Fay, that's guaranteed to be the shortest route.

- How many steps from Ana to Fay?
- Show the chain
- The first arrival is the shortest
Remembering where we came from
We do a normal breadth first search, but for each person we reach, we record who we came from, in a dictionary called parent. When we reach the target, we follow the parents backwards to rebuild the path. Run it. Ana, Ben, Dev, Fay. Three handshakes.
from collections import deque
from graph import friends
def shortest_path(start, goal):
parent, queue = {start: None}, deque([start])
while queue:
person = queue.popleft()
if person == goal:
path = []
while person:
path.append(person)
person = parent[person]
return path[::-1]
for f in friends[person]:
if f not in parent:
parent[f] = person
queue.append(f)
print(shortest_path("Ana", "Fay"))['Ana', 'Ben', 'Dev', 'Fay']
Also uses graph.py
friends = {
"Ana": ["Ben", "Cara"],
"Ben": ["Ana", "Dev"],
"Cara": ["Ana", "Dev", "Eli"],
"Dev": ["Ben", "Cara", "Fay"],
"Eli": ["Cara"],
"Fay": ["Dev"],
}Where it is used
This exact algorithm powers degrees of separation on social networks, the fewest moves to solve a puzzle, and the fewest hops for a message across a network. When every step costs the same, breadth first search finds the shortest path, in O of V plus E.
| key | value |
|---|---|
| Social networks | degrees of separation |
| Puzzles | fewest moves |
| Networks | fewest hops |
| Rule | all steps cost the same |
Summary
Breadth first search finds shortest paths when every step costs the same. Record each node's parent, then walk back from the goal. Next, graphs hiding inside grids.
Key takeaways- BFS from the start
- Record parents
- Walk back from the goal