AI Hints
Home›DSA in Python Tutorial›Graph Searches
DSA in Python · Lesson 80 of 132

Shortest Paths

Fewest steps with BFS.

⏱ 2 min read▶ Video at 1:34:49🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Shortest Paths
From the video: Shortest Paths
  • 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.

shortest.pypython
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"))
Output
['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.

keyvalue
Social networksdegrees of separation
Puzzlesfewest moves
Networksfewest hops
Ruleall 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
Next up: Practice: Counting Islands — graphs in a grid