The fewest changes on the bus
A travel app tells you how to cross town with the fewest bus stops. In a game, an enemy walks the shortest way round the walls to reach you.
Both are the same problem. Both are solved by an algorithm that only needs a queue and a little patience.
By the end of this lesson
Note
I can find a shortest path.
Key words
| Word | What it means |
|---|---|
| Graph | a set of points joined by lines |
| Node | one point in a graph, such as a bus stop |
| Edge | a line joining two nodes, such as a road |
| Neighbour | a node one edge away |
| Breadth-first search | visiting nodes in rings, nearest first, using a queue |
| Shortest path | the route with the fewest edges |
The cells students fill in are left blank in this preview.
A graph is nodes and edges
A graph is a set of nodes joined by edges. Bus stops and roads, friends on a social app, and rooms in a game are all graphs.
In Python a dictionary can hold a graph. Each key is a node, and its value is the list of its neighbours. A road goes both ways, so each stop is in the other's list.
A town's bus stops as a graph
# Bus stops, and the stops you can reach in one hop from each.
stops = {
"Station": ["Market", "Library"],
"Market": ["Station", "Park", "Cinema"],
"Library": ["Station", "School"],
"Park": ["Market", "School", "Pool"],
"School": ["Library", "Park"],
"Cinema": ["Market", "Pool"],
"Pool": ["Park", "Cinema"],
}
print("from Park you can reach:", stops["Park"])
print("number of stops:", len(stops))
# Add a new stop "Gym" next to "Pool".
# It must go in two lists. Why?
Breadth-first search visits in rings
Breadth-first search starts at one node. It visits every neighbour first, then their neighbours, ring by ring.
A queue keeps the order. Take a node from the front, and add each neighbour not yet seen to the back with one more hop. Because nearer nodes always leave the queue first, each node is first reached by a shortest path.
Worked example: searching from Station
| Visit | Hops | Queue after |
|---|---|---|
| Station | 0 | Market, Library |
| Market | 1 | Library, Park, Cinema |
| Library | 1 | Park, Cinema, School |
| Park | 2 | Cinema, School, Pool |
| Cinema | 2 | School, Pool |
| School | 2 | Pool |
| Pool | 3 | empty |
The cells students fill in are left blank in this preview.
Breadth-first search with a queue
# Breadth-first search: visit the stops in rings, nearest first.
stops = {
"Station": ["Market", "Library"],
"Market": ["Station", "Park", "Cinema"],
"Library": ["Station", "School"],
"Park": ["Market", "School", "Pool"],
"School": ["Library", "Park"],
"Cinema": ["Market", "Pool"],
"Pool": ["Park", "Cinema"],
}
start = "Station"
hops = {start: 0}
queue = [start]
while len(queue) > 0:
here = queue.pop(0)
print("visit", here, "hops:", hops[here])
for next_stop in stops[here]:
if next_stop not in hops:
hops[next_stop] = hops[here] + 1
queue.append(next_stop)
# Change start to "Pool". Which stops are furthest away now?
A common mistake
Warning
Many people think breadth-first search finds the quickest route in minutes or miles. It finds the fewest edges, because every edge counts as one hop. When roads have different lengths, a map app needs another algorithm that adds up the lengths.
Graphs in the lab with NetworkX
The lab has NetworkX, a Python library for graphs. Type the cell below into your notebook. It builds the same town from your dictionary, finds the shortest path and draws the map.
Then the Run times NetworkX on a grid of streets, 30 by 30, which has 900 junctions.
Type this in your notebook: the town
import networkx as nx
stops = {
"Station": ["Market", "Library"],
"Market": ["Station", "Park", "Cinema"],
"Library": ["Station", "School"],
"Park": ["Market", "School", "Pool"],
"School": ["Library", "Park"],
"Cinema": ["Market", "Pool"],
"Pool": ["Park", "Cinema"],
}
town = nx.Graph(stops)
print(town.number_of_nodes(), "stops,", town.number_of_edges(), "roads")
print(nx.shortest_path(town, "Station", "Pool"))
print(nx.shortest_path_length(town, "Station", "Pool"), "hops")
nx.draw(town, with_labels=True, node_color="lightblue")
Time a search across 900 junctions
docker exec jupyter python3 -m timeit -s "import networkx as nx" -s "g = nx.grid_2d_graph(30, 30)" "nx.shortest_path(g, (0, 0), (29, 29))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Going further: roads with lengths
Give each road in your notebook a length with town.add_edge("Market", "Park", weight=5), and so on for every road.
Ask nx.shortest_path again with weight="weight". Can you choose lengths that make the fewest-hops route lose?