Finding the shortest route through a network
Breadth-first search explores a graph, a set of things joined by links, one step at a time. The first path it finds has the fewest links. It is how a map app finds the fewest changes between stations, and how a network tool finds the fewest hops between two machines.
In this lesson the graph is a small office network, and the question is how many links lie between the laptop and the backup server.
By the end of this lesson
Note
I can find a path with breadth-first search.
Key words
| Word | What it means |
|---|---|
| Graph | nodes joined by links |
| Node | one thing in the graph, such as a machine |
| Edge | a link between two nodes |
| Neighbour | a node joined directly to another |
| Queue | a line where the first in is the first out |
| Visited | already reached, so not added again |
The cells students fill in are left blank in this preview.
A graph is nodes joined by edges
A graph has nodes and edges. Here each node is a machine and each edge is a cable between two machines. Two nodes joined by an edge are neighbours.
In Python you can keep a graph as a dictionary. Each key is a node, and its value is the list of its neighbours.
A graph as a dictionary
# A graph as a dictionary: each machine maps to the machines it links to.
graph = {
"laptop": ["router"],
"router": ["laptop", "web", "files"],
"web": ["router", "db", "cache"],
"files": ["router", "backup"],
"db": ["web", "backup"],
"cache": ["web"],
"backup": ["files", "db"],
}
print("router links to", graph["router"])
print("the web server has", len(graph["web"]), "neighbours")
# Change "router" to "backup" in both lines and run again.
A list of links in a file
Network tools often keep a graph as a list of edges, one per line. The first Run writes seven edges to a file. The others search it: grep prints the lines that mention the router, and -c counts them.
Each line holds two machine names with a space between.
Write the seven links to a file
printf 'laptop router\nrouter web\nrouter files\nweb db\nweb cache\nfiles backup\ndb backup\n' > links.txtShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Which links mention the router?
grep router links.txtShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
How many links mention the router?
grep -c router links.txtShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
How many links in all?
wc -l links.txtShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Breadth-first search visits the nearest nodes first
Breadth-first search starts at one node. It visits every node one link away, then every node two links away, and so on, like ripples in water.
A queue keeps the order. Take the front node, add its unvisited neighbours to the back, and note how far each is. The first time you reach a node is by the fewest links.
Worked example: from the laptop
| Take from front | Added to the back | Queue afterwards |
|---|---|---|
| laptop (0 links) | router (1) | router |
| router | web (2), files (2) | web, files |
| web | db (3), cache (3) | files, db, cache |
| files | backup (3) | db, cache, backup |
| db, cache, backup | Nothing new | Empty: finished |
The cells students fill in are left blank in this preview.
Run breadth-first search
# Breadth-first search: how many links from the laptop to every machine?
graph = {
"laptop": ["router"],
"router": ["laptop", "web", "files"],
"web": ["router", "db", "cache"],
"files": ["router", "backup"],
"db": ["web", "backup"],
"cache": ["web"],
"backup": ["files", "db"],
}
start = "laptop"
distance = {start: 0}
queue = [start]
while len(queue) > 0:
current = queue.pop(0)
for neighbour in graph[current]:
if neighbour not in distance:
distance[neighbour] = distance[current] + 1
queue.append(neighbour)
print(distance)
# Change start to "cache" and run again.
It counts links, not cost
Breadth-first search finds the path with the fewest links. That is not always the cheapest path, because links can differ in cost, such as distance or delay.
Finding the cheapest path needs a method that adds up the costs, such as Dijkstra's algorithm. It follows the same idea with a smarter queue.
Worked example: fewest links is not cheapest
| Route | Links | Total delay |
|---|---|---|
| laptop, router, files, backup | 3 | 90 milliseconds |
| laptop, router, web, db, backup | 4 | 25 milliseconds |
The cells students fill in are left blank in this preview.
A common mistake
Warning
Many people think the search ends on its own once it has seen every node. In a graph with a loop it does not: A leads to B, B leads back to A, and the queue never empties. Keep a record of the nodes you have reached and add a node only the first time.