Shortest routes in a network
In a tree, exactly one route joins any two nodes. A network of computers or a road map is not like that: two places can be joined by many routes, and the usual question is how long the shortest one is. Breadth-first search (BFS) finds the shortest route when the length of a route is the number of connections on it. We will build it on this problem:
A network has computers, numbered 1 to , and two-way connections between pairs of them. Uolevi's computer is 1 and Maija's is . Find the smallest number of computers on a route that carries a message from 1 to , and print one such route.
The first input line holds and ; each of the next lines holds a connection . Print the number of computers and then the route, or IMPOSSIBLE if no route exists.
Constraints
Sample · Input
5 5 1 2 1 3 1 4 2 3 5 4
Output
3 1 4 5
In the sample, computer 1 is connected to 2, 3 and 4, computers 2 and 3 are connected to each other, and computer 5 is connected only to 4. A message from 1 to 5 has to pass through 4, so the route 1, 4, 5 uses three computers. No route uses two, because 1 and 5 are not connected directly.
One way to solve the problem is to list every route from computer 1 to computer and keep the shortest. On a large network that is hopeless, because every place where the network offers two ways forward doubles the number of routes.
Picture 31 computers in a row, none of them connected directly to the next. Instead, each gap between two neighbors in the row holds two relay computers, and each relay is connected to both of those neighbors. That is only computers, but a route from the first computer of the row to the last picks one of the two relays at each of the 30 gaps, and each combination of picks is a different route:
Message Route allows 100,000 computers, so we need a method that does not go through the routes one by one.
The order of the search
Breadth-first search finds the computers in order of how far they are from the start: first the start itself, then every computer one connection away, then every computer two connections away, and so on until nothing new turns up. Here is the sample with each computer drawn under its distance from computer 1:
The search finds computer 1, then 2, 3 and 4, then 5. Each computer is found once, at the smallest number of connections that reaches it (we will see why once the search is written down). So when computer is found, we know the length of the shortest route to it.
To write the search as a program we need two things: a way to store the network so that the computers next to a given one are quick to look up, and a way to visit the computers in this order.
Graphs and adjacency lists
The network in Message Route is a graph: a set of objects called vertices, or nodes, together with edges, each of which joins a pair of vertices. The computers are the vertices and the connections are the edges. A graph can describe anything built from pairs: road junctions and the streets between them, or the courses of a university, with an edge between two courses that share a student and so cannot hold their exams at the same time.
A tree is a graph too, the kind in which exactly one route joins any two vertices. In other graphs two vertices can be joined by several routes, as 1 and 3 are in the sample, or by none.
In a graph, a route that goes from vertex to vertex along edges is called a path, and its length is the number of edges on it. The distance from one vertex to another is the length of the shortest path between them. The path 1, 4, 5 has two edges and no path from 1 to 5 has fewer, so the distance from 1 to 5 is 2. Message Route counts the computers on the path, which is always one more than the number of edges, so its answer is the distance plus 1.
A connection in Message Route carries messages both ways, which makes the graph undirected. In a directed graph each edge points one way, like a one-way street, and we write an edge from to as u → v.
The search will need, again and again, the vertices that are one edge away from a given vertex. Those are the vertex's neighbors. Scanning the whole list of edges each time would cost steps, where is the number of edges, so before searching we build an adjacency list: for each vertex, a list of its neighbors. An undirected edge between and puts in the list of and in the list of , and a directed edge a → b puts only in the list of . For the sample the lists are:
Every edge appears in two lists, so the lists hold numbers in all: 10 for the sample, and at most 400,000 for the largest input.
Deeper read: the adjacency matrix
A graph can also be stored as an adjacency matrix: a table with a row and a column for every vertex, whose entry in row and column says whether there is an edge from to . It answers "are these two vertices joined?" in one read. But the search asks for all the neighbors of a vertex, and in a matrix that means scanning a whole row of entries. The table also has entries however few edges there are. At Message Route's limits, and :
At four bytes an entry, the matrix would need 40 gigabytes.
A matrix still has its uses. In a dense graph, where most pairs of vertices are joined, the lists hold nearly numbers as well, so the matrix costs little more memory and keeps its one-read answer to whether two vertices are joined.
A matrix can also be multiplied, and some questions about a graph are answered by matrix arithmetic. Write 1 for an edge and 0 for none, and multiply the matrix by itself: the entry in row and column of the product counts the vertices with an edge from to and an edge from to , which is the number of ways to go from to along exactly two edges. For the sample, the entry for computers 1 and 5 is 1, for the route 1, 4, 5.
Visit the vertices in order of distance
The search has to deal with every vertex at distance 1 before any vertex at distance 2, and with those before any at distance 3. A queue gives that order, because it hands its entries back first in, first out. The vertices at distance 1 join the queue while the neighbors of the start are read, so they all leave before the vertices at distance 2 that they add behind them.
This is how a queue visits a tree level by level, with one change. In a graph an edge can lead to a vertex the search has already found, and the search must not add that vertex to the queue a second time. So we record which vertices have been found, in the array distance. It has one entry per vertex and starts at everywhere, which means "not found yet". The search has four steps:
- Set the distance of the start to 0 and put the start in the queue.
- Take the vertex at the front of the queue. Call it .
- For each neighbor of whose distance is still , set the distance of to the distance of plus 1, and add at the back of the queue.
- Repeat steps 2 and 3 until the queue is empty.
Here is the search on the sample, from computer 1. After step 1, only computer 1 has a distance:
distance are the computers. In each drawing, the highlighted entries are the ones that were just set.We take 1 from the queue. Its neighbors are 2, 3 and 4, and all three are still at , so each gets distance and joins the queue:
Next we take 2. Its neighbors are 1 and 3, and both already have a distance, so no distance changes. The edge from 2 to 3 is part of the longer route 1, 2, 3, which would put computer 3 at distance 2; computer 3 keeps the distance 1 it already has. Taking 3 finds no new vertex either. Then we take 4, whose neighbor 5 is still at , so 5 gets distance :
Finally we take 5, which has no new neighbor, and the queue is empty. Computer 5 is at distance 2, so the shortest route to it has two connections and three computers, as the sample says.
The search in code
In code, the four steps are a loop around a queue. The program builds the adjacency lists of the sample and prints the distance of every computer from computer 1. Computers are numbered from 1, so each array has entries and entry 0 is not used.
def bfs_distances(n, graph, start):
distance = [-1] * (n + 1)
distance[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in graph[u]:
if distance[v] == -1:
distance[v] = distance[u] + 1
queue.append(v)
return distance
n = 5
edges = [(1, 2), (1, 3), (1, 4), (2, 3), (5, 4)]
graph = [[] for _ in range(n + 1)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
print(bfs_distances(n, graph, 1)[1:])The program prints [0, 1, 1, 1, 2], the distances we found by hand.
The test distance[v] == -1 is what stops the search from going round in circles. In the sample, computers 1, 2 and 3 form a triangle, and without the test they would keep adding one another to the queue.
Cost of the search
- Listing every route
exponential - The row of 31 computers with two relays in each gap has routes.
- Building the adjacency lists
- One pass over the edges puts numbers into lists.
- The search
- A vertex gets its distance at the moment it joins the queue, so it joins once, and its adjacency list is read once, when it leaves.
For the largest Message Route input:
That is far inside a budget of about steps a second.
Why the distances are shortest
The search writes a number for each vertex once, the first time it meets the vertex, and never revises it. Until we know that this number is the vertex's distance, we call it its label.
At first the queue holds only the start, with label 0. A vertex taken from the front with label gives the label to the vertices it finds, and they go to the back, behind every vertex still waiting with label . So all the vertices labelled leave before the first one labelled , and only then do labels appear. At any moment the queue holds at most two different labels, the smaller in front:
So the search hands out its labels in increasing order: 0 first, then all the 1s, then all the 2s. We show in two steps that every label is the true distance.
First, a label is never too small, because it is always the length of a real path. The label of the start, 0, is the length of the path that stays at the start. Every other vertex gets its label while the neighbors of some vertex are being read, and the label is one more than the label of . If the label of is the length of a path from the start to , then that path followed by the edge from to is a path to whose length is the label of .
Second, a label is never too large: it is at most the length of any path to its vertex. Take a path from the start to with edges, and call its vertices , so that is the start and is . We check along the path that each gets a label of at most . The label of the start is 0. Now suppose has a label of at most . Then it joined the queue, and when it leaves, the search reads its neighbors, among them.
If has no label yet, it gets the label of plus 1, which is at most . If it has one already, that label was handed out earlier, and since labels come out in increasing order, it is no larger than the label of plus 1, the label handed out while the neighbors of are read. Either way the label of is at most , and at the end of the path the label of is at most .
Put together, the label of is the length of some path to , and no path to has fewer edges, so the label is the distance of .
A vertex with no path from the start is never found. It is still at when the queue empties, and Message Route then prints IMPOSSIBLE.
The search is correct only when every edge counts as one step. If edges have different lengths, as roads measured in minutes do, a path with more edges can be the shorter one, and the first distance a vertex gets can be wrong. The 0-1 BFS page handles edges that cost 0 or 1, and the Shortest paths lesson handles other lengths.
A directed example
The next example has two things the sample lacks, one-way edges and a vertex that cannot be reached. It is a directed graph with six vertices numbered from 0. Its edges are 0 → 1, 0 → 2, 1 → 3, 3 → 4, 2 → 4 and 4 → 1, and vertex 5 has no edges. Each vertex is drawn with its distance from vertex 0:
Vertex 4 can be reached along 0 → 1 → 3 → 4, with three edges, or along 0 → 2 → 4, with two. The dashed edges lead to a vertex that was already found when the search read them.
Worked example
Step through the search
The trace runs the program on this graph one step at a time. Watch for the step that reads the edge 3 → 4: vertex 4 already has distance 2 from the route through 2, so the edge is skipped. Vertex 5 ends at . The row named parent records, for each vertex, the vertex it was found from, and the next part uses it. The second preset starts the search from vertex 3, from which vertices 0 and 2 cannot be reached.
Discover vertex 0 at distance 0 and add it to the queue. Other vertices have distance -1.
- start
- 0
Change the example input
Current result: [0,1,1,2,2,-1]
Rebuild the route from parents
Message Route asks for the route as well as its length. The distances alone do not give it, but one more array does. Whenever the search finds a vertex from a vertex , it also records parent[v] = u, the vertex it came from. After the search on the sample the two arrays are:
The parent of a vertex is one step closer to the start than the vertex is. So if we begin at the target and keep moving to the parent, we arrive at the start, and the vertices we pass are a shortest path read backwards. From computer 5, parent[5] is 4 and parent[4] is 1, which is the start. That gives 5, 4, 1, and reversed it is the route 1, 4, 5.
Every vertex the search finds, apart from the start, has exactly one parent, so the parent links form a tree rooted at the start, called a shortest-path tree: the path in it from the start to any vertex is a shortest path in the graph. A graph can have several shortest paths to the same vertex. The tree keeps one of them, whichever the search happened to find first, and Message Route accepts any.
Print the route
The search is the one above with a parent array added. After the loop, the program starts a list with computer and keeps appending the parent of the last entry until that entry is computer 1. Reversing the list gives the route.
def shortest_route(n, graph):
distance = [-1] * (n + 1)
parent = [0] * (n + 1)
distance[1] = 0
queue = deque([1])
while queue:
u = queue.popleft()
for v in graph[u]:
if distance[v] == -1:
distance[v] = distance[u] + 1
parent[v] = u
queue.append(v)
if distance[n] == -1:
return []
route = [n]
while route[-1] != 1:
route.append(parent[route[-1]])
route.reverse()
return route
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
graph = [[] for _ in range(n + 1)]
for i in range(m):
a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
graph[a].append(b)
graph[b].append(a)
route = shortest_route(n, graph)
if route:
print(len(route))
print(*route)
else:
print("IMPOSSIBLE")On the sample the program prints 3 and then 1 4 5. The 3 is the length of the list, which counts computers, so no 1 has to be added to a distance. The walk back takes at most steps, so the program still runs in time.
Grids as graphs
Many problems are set on a grid, such as a maze or a game board, in which some cells are open and the others are walls. A grid is a graph as well. Each open cell is a vertex, and two open cells that share a side are joined by an edge, so the fewest moves between two cells is a distance.
A grid needs no adjacency lists, because the neighbors of a cell follow from its position. The cell in row and column has the neighbors , , and , except any that lie outside the grid or are walls. The queue holds pairs of a row and a column, and the distances go in a grid of the same shape.
The widget runs BFS from the top-left cell of a grid with two walls. Each step fills in every cell one move farther out, and the goal in the bottom-right corner ends at distance 6. Click a cell to add or remove a wall. With walls on both cells next to the goal, the search runs out of cells before it gets there.
Shortest Path in Binary Matrix, in this page's problem list, is this search with two changes. A path may also step diagonally, so a cell has up to eight neighbors, and the answer counts the cells on the path, which is one more than the number of moves. The next part has a complete grid search as a program.
Several starting points
Some problems have several starting points and ask how far each vertex is from the nearest of them. Here is one:
In a grid, 0 is an empty cell, 1 a fresh orange and 2 a rotten orange. Every minute, each fresh orange that shares an edge with a rotten orange becomes rotten. Return the number of minutes until no fresh orange is left, or if that never happens.
Constraints
- for an grid
- each cell is 0, 1 or 2
Sample 1 · Input
grid = [[2,1,1],[1,1,0],[0,1,1]]
Output
4
Sample 2 · Input
grid = [[2,1,1],[0,1,1],[1,0,1]]
Output
-1
Sample 3 · Input
grid = [[0,2]]
Output
0
Each minute the rot spreads one step from every rotten orange at once. So the minute at which a fresh orange rots is its distance from the nearest orange that was rotten at the start, along a path that passes only through oranges. The answer is the largest of those distances, or if some fresh orange has no such path.
One BFS from each rotten orange, keeping the smallest distance found for each cell, would give these distances, but it searches the grid once per rotten orange. One search is enough if we put every rotten orange in the queue before the loop begins, each at distance 0, and leave the loop as it was. The queue then gives back all the starting points first, then every cell one step from some starting point, then every cell two steps from its nearest one.
The starting points are called sources, and the search is called multi-source BFS. The grid widget in the previous part can run one: choose "Click toggles sources", click a second cell, and the distances spread from both.
To see that these distances are right, imagine one extra vertex with an edge to every starting point. An ordinary BFS from finds all the starting points at distance 1 and then does exactly what our search does, with every distance one larger. So our search computes the distance from minus 1, which is the distance to the nearest starting point.
Each of the three samples has a single rotten orange. In the first it is in the top-left corner, and the last fresh orange rots at minute 4:
In the second sample the orange in the bottom-left corner has empty cells above it and to its right, so the search does not reach it and the answer is .
Put every starting point in the queue first
The program keeps the minute at which each cell rots in minute, a grid of the same shape that starts at . For the cell it takes from the queue, it tries the four neighboring positions and accepts each one that is inside the grid, holds a fresh orange and has no minute yet. The last cell taken out has the largest minute, which the program keeps in answer. After the loop, a fresh orange still at was not reached.
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
minute = [[-1] * cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
minute[r][c] = 0
queue.append((r, c))
answer = 0
while queue:
r, c = queue.popleft()
answer = minute[r][c]
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and minute[nr][nc] == -1:
minute[nr][nc] = minute[r][c] + 1
queue.append((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1 and minute[r][c] == -1:
return -1
return answer
print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]),
oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]),
oranges_rotting([[0, 2]]),
oranges_rotting([[2, 1, 1, 1, 2]]))For the three samples the program prints 4, and 0; the third has no fresh orange to wait for. The fourth call is a grid of our own with two rotten oranges, one at each end of a row of five. The middle orange is two steps from both, so the program prints 2. With only one end rotten it would print 4.
States as vertices
In some BFS problems the statement mentions no graph, and the main work is finding one. One way is to make a vertex of every state, meaning every arrangement the puzzle can be in, and to join two states by an edge when one move turns the first into the second. The fewest moves from one state to another is then a distance.
A lock has four wheels, each showing a digit from 0 to 9. One move turns one wheel by one slot in either direction, and 9 and 0 wrap around to each other. The lock starts at "0000". Codes in deadends jam the lock, so no route may pass through them. Return the fewest moves to reach target, or if it cannot be reached.
Constraints
-
deadends.length - every code has 4 digits
targetis not indeadends
Sample 1 · Input
deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output
6
Sample 2 · Input
deadends = ["8888"], target = "0009"
Output
1
Sample 3 · Input
deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output
-1
A state of the lock is the four digits it shows, so there are states. Each has 8 neighbors, since any of the four wheels can turn one slot up or down. A dead end is a state the search must not enter.
As on a grid, the program does not store this graph. It works out the neighbors of a state when it takes the state from the queue. A state is a string and cannot index an array, so the distances go in a hash map, and a state that is not in the map has not been found yet.
In the first sample the target 0202 would be four turns from 0000 if there were no dead ends: two turns of the second wheel and two of the fourth. The left half of the figure has every way of making those four turns, and each passes through a dead end. The search finds a route of six moves that turns the first wheel up at the start and back down at the end.
0202 stays inside the square on the left and passes a dead end. The 6-move route on the right goes around them.Generate the eight turns of each code
The loop over step turns a wheel up with 1 and down with 9: adding 9 and taking the remainder by 10 is the same as subtracting 1, with 0 wrapping around to 9. The program returns as soon as it takes the target from the queue, which is safe because a distance does not change once it is set. It returns before searching if 0000 is itself a dead end.
def open_lock(deadends, target):
dead = set(deadends)
if "0000" in dead:
return -1
turns = {"0000": 0}
queue = deque(["0000"])
while queue:
code = queue.popleft()
if code == target:
return turns[code]
for i in range(4):
digit = int(code[i])
for step in (1, 9):
turned = code[:i] + str((digit + step) % 10) + code[i + 1:]
if turned not in dead and turned not in turns:
turns[turned] = turns[code] + 1
queue.append(turned)
return -1
print(open_lock(["0201", "0101", "0102", "1212", "2002"], "0202"),
open_lock(["8888"], "0009"),
open_lock(["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"], "8888"))In the second sample one turn of the last wheel takes 0000 down to 0009. In the third, all eight neighbors of 8888 are dead ends, so the queue empties without 8888 being found. At worst the search takes every state from the queue and tries its 8 neighbors:
Neighbors that depend on the input
In the next problem a state has no fixed set of neighbors. They depend on a list of words given in the input.
You get a begin word, an end word and a word list. One step changes a single letter, and every word after the begin word must be in the list. Return the number of words in the shortest sequence from the begin word to the end word, or 0 if there is none.
Constraints
- word length
-
wordList.length - all words have the same length and use lowercase letters
- the words in the list are distinct
Sample 1 · Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
5
Sample 2 · Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output
0
The states are words, and two words are neighbors when they differ in exactly one position. In the first sample the shortest sequence is hit, hot, dot, dog, cog. The answer counts its words, 5, so the search stores lengths that start at 1, one more than the distance.
The neighbors of a word could be found by comparing it with every word in the list, which over the whole search compares every pair of words. It is cheaper to build every string that differs from the word in one position, trying each of the 26 letters there, and to keep those that are in a hash set of the list. For the largest input, 5,000 words of 10 letters:
Building candidates does about a nineteenth of the work.
Try every one-letter change
The program builds the candidates with two loops, one over the positions of the word and one over the 26 letters.
def ladder_length(begin_word, end_word, word_list):
words = set(word_list)
if end_word not in words:
return 0
length = {begin_word: 1}
queue = deque([begin_word])
while queue:
word = queue.popleft()
if word == end_word:
return length[word]
for i in range(len(word)):
for letter in "abcdefghijklmnopqrstuvwxyz":
changed = word[:i] + letter + word[i + 1:]
if changed in words and changed not in length:
length[changed] = length[word] + 1
queue.append(changed)
return 0
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]),
ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))In the second sample cog is not in the list, and the program returns 0 without searching. One of the 26 letters in each position gives back the word itself, which is already in length and is skipped.
Common BFS mistakes
Marking a vertex as found when it leaves the queue.
- Where it breaks
- On the Message Route sample, computer 2 leaves the queue while 3 is still waiting in it, not yet marked. The edge from 2 to 3 then sets the distance of 3 to and adds 3 a second time. The program reports the distances
0 1 2 1 2, but the right ones are0 1 1 1 2. - The fix
- Mark a vertex in the same step that adds it to the queue. The program above uses
distanceitself as the mark, so there is no second array to update.
Storing an undirected edge in one adjacency list only.
- Where it breaks
- The sample writes its last connection as
5 4. Stored only as 4 in the list of 5, it gives computer 4 no edge to 5. The search from 1 does not find 5, and the program printsIMPOSSIBLEalthough the answer is 3. - The fix
- Add an undirected edge to both lists. Only a directed edge goes in one.
Recall An undirected graph has the edges 1-2, 1-3, 2-4, 3-4 and 4-5, given in that order. BFS starts at vertex 1. What route to vertex 5 do the parents give, and what changes if the edge 1-3 is given first?
The queue takes the vertices in the order 1, 2, 3, 4, 5, and the distances of vertices 1 to 5 are 0, 1, 1, 2, 3. Vertex 4 is found from 2, which leaves the queue before 3, so parent[4] is 2 and the walk back from 5 gives the route 1, 2, 4, 5. With the edge 1-3 first, vertex 3 enters the queue before 2 and finds 4, so parent[4] is 3 and the route is 1, 3, 4, 5. The order of the edges can change which shortest route the search reports, but it cannot change a distance.