Graphs with weights on the edges
Breadth-first search counts every edge the same, and the shortest path it finds is the one with the fewest edges. A road map is different. One road takes 1 minute and another takes 10, and the route we want is the one that takes the least time, however many roads it uses. A graph in which every edge carries a number is called a weighted graph, and the number is the weight of the edge. A weight can stand for minutes, for a length in kilometres or for the price of a ticket.
The courier map
Our example for the whole lesson is the map of a courier. It has five towns, numbered 0 to 4, and five one-way roads. The number on a road is the time it takes in minutes:
The length of a path in a weighted graph is the sum of the weights of its edges. On the map, the path 0 → 1 → 3 has length , and the path 0 → 2 → 1 → 3 has length , although it uses one more road. As before, the distance from one vertex to another is the length of the shortest path between them, so the distance from town 0 to town 3 is 4. No road leads into town 4, so no path reaches it, and we say that its distance is infinite, written .
The problem of this lesson is to find the distance from one starting vertex, called the source, to every other vertex. For the courier map with town 0 as the source, the answer is:
A weighted graph is stored in adjacency lists like any other graph, with one change: each entry is a pair, made of the neighbor and the weight of the edge that leads to it. These are the lists of the courier map:
graph[0] (1, 4) (2, 1)graph[1] (3, 1)graph[2] (1, 2) (3, 5)graph[3]graph[4]The pair (1, 2) in the list of town 2 is the road from town 2 to town 1, which takes 2 minutes.
Breadth-first search on a weighted graph
Breadth-first search does not find these distances. Started at town 0, it reaches town 1 over the direct road of 4 minutes, and it keeps the first path it finds to each vertex, so town 1 ends up at 4. The path through town 2 takes only minutes, but it has two edges, and BFS reaches every vertex it can over one edge before it looks at any path of two. BFS finds the path with the fewest edges, and in a weighted graph that path can be the longer one.
There are two kinds of weights for which BFS, or a small change to it, still works. The first is when all the weights are equal. If every edge has weight , a path of edges has length , so the path with the fewest edges is also the shortest, and the distance is the BFS distance multiplied by .
The second is when every weight is 0 or 1, and then a variant called 0-1 BFS works. It keeps the vertices to visit in a deque, a queue that can be added to at either end. A neighbor reached over an edge of weight 0 is as far from the source as the vertex it was reached from, so it goes to the front. A neighbor reached over an edge of weight 1 is one farther, so it goes to the back.
Each entry goes into the deque with the distance its vertex has at that moment. Read by those distances, the deque holds at most two values, the smaller one in front, so the entry taken from the front is always one of the closest, as in ordinary BFS. A vertex can be reached first over an edge of weight 1 and later by a shorter path. Its distance is then lowered and it goes into the deque again, while the older entry keeps the larger distance it was added with; it comes out later and improves nothing. In the next problem the weights are not given as such and have to be read off the grid:
You get an grid of 0s, empty cells, and 1s, obstacles. Start at the top-left cell and move up, down, left or right. Return the fewest obstacles you must remove to reach the bottom-right cell.
Constraints
- Every cell is 0 or 1
- The top-left and bottom-right cells are 0
Sample 1 · Input
grid = [[0,1,1],[1,1,0],[1,1,0]]
Output
2
Sample 2 · Input
grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output
0
In the first sample every path to the bottom-right corner crosses at least two obstacles. In the second, a path of empty cells leads down the left column, along the bottom row, up the third column, along the top row and down the last column, so nothing has to be removed.
The cells are the vertices, and each move to a neighboring cell is an edge. We give a move the weight of the cell it enters: 1 if that cell holds an obstacle, which has to be removed, and 0 if it is empty. The length of a path is then the number of obstacles on it, and the answer is the distance from the top-left cell to the bottom-right one.
INF = float("inf")
def minimum_obstacles(grid):
rows, cols = len(grid), len(grid[0])
dist = [[INF] * cols for _ in range(rows)]
dist[0][0] = 0
queue = deque([(0, 0)])
while queue:
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols:
w = grid[nr][nc] # the weight of this move
if dist[r][c] + w < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + w
if w == 0:
queue.appendleft((nr, nc)) # weight 0: to the front
else:
queue.append((nr, nc)) # weight 1: to the back
return dist[rows - 1][cols - 1]
print(minimum_obstacles([[0, 1, 1], [1, 1, 0], [1, 1, 0]]))
print(minimum_obstacles([[0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0]]))The last two lines run the official samples.
The grid has at most cells, and each of them enters the deque at most twice. When a cell first gets a distance, it is or , where is the distance of the cell just taken from the front, and no cell taken later is closer than . So the distance of a cell can drop at most once, from to . The search therefore takes at most cells from the deque and checks at most moves.
With weights such as 4, 1, 2 and 5, neither method applies. The deque stayed in order because each new vertex was 0 or 1 farther than the one just taken, so it belonged at the front or at the back. A road of 5 minutes leads to a vertex that may belong anywhere in between. The rest of this lesson is about weights like these.
Tentative distances and relaxation
Every algorithm in this lesson keeps an array dist with one entry for each vertex. The entry dist[v] is the length of the shortest path to that the algorithm has found so far, and it is called the tentative distance of . At the start the only path we know is the empty one from the source to itself, so dist is 0 for the source and for every other vertex.
Tentative distances are improved one edge at a time. Take an edge with weight . If we know a path to of length dist[u], then following that path and crossing the edge is a path to of length dist[u] + w. If that is less than dist[v], we have found a shorter path to than any before, and we store its length:
This step is called relaxing the edge. In the figure it is done twice: on the left it lowers the distance of , and on the right the distance of stays as it is.
On the courier map we start from the initial array and relax three roads in turn. The road 0 → 1 gives town 1 the tentative distance , and the road 0 → 2 gives town 2 the distance . Then the road 2 → 1 offers town 1 a path of length , which is less than 4, so dist[1] drops to 3:
dist after each relaxation. The highlighted entry is the one that changed.A tentative distance is always the length of a path that exists, so it is never smaller than the true distance. Relaxation can only bring it down towards the true distance, and once it gets there it stays. Relaxing an edge while dist[u] is still changes nothing, because no path to is known yet.
Relax every edge until nothing changes
Relaxation gives us a first algorithm at once. We go through the list of edges and relax each one, and we call one such pass over all the edges a round. We repeat rounds until a whole round lowers no distance. This is the Bellman-Ford algorithm.
Suppose the roads of the courier map are listed in the order 1 → 3, 2 → 1, 2 → 3, 0 → 1, 0 → 2. In round 1 the first three roads start at towns whose distance is still and do nothing, and the last two give towns 1 and 2 the distances 4 and 1. In round 2, 1 → 3 gives town 3 the distance , and then 2 → 1 lowers town 1 to 3. Round 3 relaxes 1 → 3 again, now with the better distance of town 1, and town 3 drops to 4. Round 4 changes nothing, and the algorithm stops:
dist after each round. The highlighted entries changed in that round.When a round changes nothing, the distances are correct. At that point no edge can be relaxed, so dist[v] is at most dist[u] + w for every edge with weight . Now take any path from the source to a vertex and walk along it. The source has dist 0, and each time we cross an edge of the path, dist[v] is at most dist[u] plus the weight of that edge. Added up along the path, this says that dist[t] is at most the length of the whole path. That holds for every path to , the shortest one included, and dist[t] is never smaller than the true distance, so the two are equal.
The function below is this algorithm. edges is a list of triples , one for each edge with weight . The loop stops at the first round that changes nothing. It also has an upper limit of rounds, where is the number of vertices. Why rounds are enough is shown on the Bellman-Ford page of this lesson.
INF = float("inf")
def shortest_paths(n, edges, source):
dist = [INF] * n
dist[source] = 0
for _ in range(n - 1): # n - 1 rounds are always enough
changed = False
for u, v, w in edges:
if dist[u] + w < dist[v]: # relax the edge u -> v
dist[v] = dist[u] + w
changed = True
if not changed:
break
return dist
roads = [(1, 3, 1), (2, 1, 2), (2, 3, 5), (0, 1, 4), (0, 2, 1)]
print(shortest_paths(5, roads, 0))The last two lines run the courier map with its roads in the order used above. Python prints infinity as inf.
Step through the rounds
The widget relaxes one road at a time, in the same order as above. Its switch is set to Update in place, which is what our function does: each relaxation reads the distances as they are at that moment. The other setting and the other examples come later in this lesson.
A round relaxes every edge once, so with edges it takes steps, and there can be up to rounds. For a graph with vertices and edges, the limits of CSES Shortest Routes I, that is
which is more than half an hour at the roughly steps a second of a loop written in Python.
Most of these relaxations change nothing. In the example the four rounds relaxed 20 edges, and only 5 of those relaxations lowered a distance. The road 1 → 3 was relaxed four times: once while town 1 was still at , once with the distance 4, once with the final distance 3, and once more in the last round. Had we waited until the distance of town 1 was final, one relaxation of that road would have been enough. Dijkstra's algorithm, on the next page, relaxes the edges in an order that makes this true for every edge.
Cost of the methods on this page
- BFS, when all weights are equal
time - Breadth-first search, with every distance multiplied by the common weight at the end.
- 0-1 BFS, for weights 0 and 1
time - Each vertex enters the deque at most twice. Minimum Obstacle Removal has at most cells and fewer than moves.
- Relaxing every edge in rounds
time - At most rounds of relaxations: about for vertices and edges.
- Memory
- The adjacency lists or the list of edges, and one distance for each vertex.
Common mistakes with weighted graphs
Running plain BFS on a graph whose weights differ, and adding up the weights along the way.
- Where it breaks
- On the courier map BFS reaches town 1 over the direct road and town 3 from town 1, and reports
[0, 4, 1, 5, inf]. The distances of towns 1 and 3 are 3 and 4. - The fix
- BFS is for equal weights. With weights of 0 and 1 use 0-1 BFS, and with other weights that are not negative use Dijkstra's algorithm.
Relaxing every edge once and stopping.
- Where it breaks
- With the roads in the order
1 → 3,2 → 1,2 → 3,0 → 1,0 → 2, one round leaves[0, 4, 1, inf, inf]: town 1 is at 4 where it should be at 3, and town 3 looks as if it could not be reached. - The fix
- Repeat the rounds until one of them changes nothing.
Recall The roads of the courier map are relaxed in rounds in the order `2 → 3`, `1 → 3`, `0 → 2`, `2 → 1`, `0 → 1`. What is `dist` after round 1 and after round 2, and which round is the first to change nothing?
In round 1 the first two roads start at towns that are still at . Then 0 → 2 gives town 2 the distance 1, 2 → 1 gives town 1 the distance , and 0 → 1 offers 4, which is not better. After round 1 the array is [0, 3, 1, ∞, ∞]. In round 2, 2 → 3 gives town 3 the distance 6 and 1 → 3 lowers it to , so the array is [0, 3, 1, 4, ∞]. Round 3 changes nothing.