Graphs with negative weights
A weight does not have to be a time or a price. In a game it can be the change in a score when we walk through a tunnel, and that change can be negative. Dijkstra's algorithm must not be used on such a graph: one road of negative weight on the courier map was enough to make it give a wrong distance.
The courier map with a negative road
Here is that map again, with the two extra roads 0 → 4 of weight 6 and 4 → 1 of weight :
The algorithm of the first page, which relaxes every edge in rounds until a round changes nothing, makes no assumption about the weights. It never treats a distance as final before the end, so a negative weight cannot arrive too late for it. That algorithm is Bellman-Ford. On this map, with the roads in the order 0 → 1, 0 → 2, 2 → 1, 1 → 3, 2 → 3, 0 → 4, 4 → 1, it runs like this:
dist after each round. The highlighted entries changed in that round.In round 1 town 1 is first given 4 and then lowered to 3 by 2 → 1, and 1 → 3 gives town 3 the distance . At the end of the round 0 → 4 gives town 4 the distance 6, and the negative road lowers town 1 to . Round 2 relaxes 1 → 3 again and brings town 3 to , the distance that Dijkstra's algorithm missed. Round 3 changes nothing.
The number of rounds
The first page said that the rounds stop after at most of them, where is the number of vertices. This follows from a statement about a single round:
After round , every vertex that has a shortest path of at most edges has its final distance.
Take the shortest path to town 3, 0 → 4 → 1 → 3, which has three edges. The distance of town 0 is right from the start. Round 1 relaxes 0 → 4 with that distance, so after round 1 town 4 is right. Round 2 relaxes 4 → 1 with the right distance of town 4, so after round 2 town 1 is right, and round 3 does the same for town 3 through 1 → 3. The edge order of our run was luckier than this: 0 → 4 is listed just before 4 → 1, so round 1 did two of the three steps.
The same argument works for every vertex and for any order of the edge list. Let have a shortest path of edges whose last edge is , with weight . The part of the path before that edge is a shortest path to , because a shorter path to , followed by the edge, would be a shorter path to . It has edges, so by the statement for round , dist[u] is final after round .
When round comes to the edge , either dist[v] is already at most dist[u] + w or the relaxation sets it to that value. Either way dist[v] is now at most the length of the shortest path, and a tentative distance is never below the true distance, so dist[v] is final.
If no cycle in the graph has weights that add up to less than 0, every vertex that can be reached has a shortest path that visits no vertex twice. A path that visits a vertex twice goes around a cycle between the two visits, and cutting that cycle out leaves a path that is no longer, since the weights on the cycle add up to 0 or more. A path that visits no vertex twice has at most edges, so after rounds every distance is final. That is rounds of relaxations each, or time, for a graph with edges.
The bound is a worst case. On our map only two rounds changed something, while the bound allows four. That is why the code stops at the first round that changes nothing: as the first page showed, the distances are correct as soon as a round changes nothing.
Negative cycles
Add one more road to the map, 3 → 4 with weight 2. The towns 4, 1 and 3 now lie on a cycle, 4 → 1 → 3 → 4, whose weights add up to . A cycle whose weights add up to less than 0 is called a negative cycle. Every lap around this one makes a path shorter by 1, so the paths to towns 4, 1 and 3 can be made as short as we like, and these towns have no shortest path at all.
On this map the rounds never reach a round that changes nothing:
dist after each round, with the road 3 → 4 added at the end of the edge list. The highlighted entries changed in that round.We can use this to detect a negative cycle. Without one, the distances are final after rounds, so round cannot lower anything. If round does lower a distance, the graph has a negative cycle that can be reached from the source. The map has 5 towns, and round 5 lowered town 1 from 1 to 0.
The test does not miss a negative cycle that can be reached. After rounds every vertex that can be reached has a finite distance, because it has a path of at most edges.
If at that point no edge of the cycle could be relaxed, dist[v] would be at most dist[u] + w for each of its edges . Add these up around the cycle: every vertex of the cycle appears once on each side, so the distances cancel, and what is left says that 0 is at most the sum of the weights. For a negative cycle that is false, so some edge of the cycle can still be relaxed, and round lowers at least one distance.
The function below runs up to rounds. It returns the distances as soon as a round changes nothing, and reports a negative cycle if round still lowered a distance.
INF = float("inf")
def bellman_ford(n, edges, source):
dist = [INF] * n
dist[source] = 0
for _ in range(n): # rounds 1 to n
changed = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed:
return dist # a round lowered nothing: the distances are final
return None # round n still lowered a distance: a negative cycle
roads = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (0, 4, 6), (4, 1, -4)]
print(bellman_ford(5, roads, 0))
print(bellman_ford(5, roads + [(3, 4, 2)], 0))The two calls run the map of this page, first as drawn and then with the road 3 → 4.
An undirected edge with a negative weight is a negative cycle by itself, because it can be crossed and crossed straight back.
Shortest paths with a limit on the number of edges
The argument for the number of rounds shows a little more: after round , each dist[v] is at most the length of the shortest path to among the paths with at most edges. With a small change, made below, the rounds compute that length exactly. The next problem asks for it, and Dijkstra's algorithm cannot find it:
There are cities numbered from 0 and one-way flights [from, to, price]. Return the cheapest price from src to dst with at most stops, that is at most flights, or -1 if there is no such route.
Constraints
-
flights.length -
price - No two flights share the same
fromandto -
src,dst, andsrcdst
Sample 1 · Input
n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output
700
Sample 2 · Input
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output
200
Sample 3 · Input
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output
500
In the first sample the answer is 700, for the flights from 0 to 1 and from 1 to 3 at . The route 0, 1, 2, 3 costs only , but it has two stops, one more than allowed.
Dijkstra's algorithm keeps one number for each city, its cheapest price, and here that is not enough. The cheapest way to reach a city may use too many flights, and a more expensive way with fewer flights may be the one that still reaches the destination. The rounds count flights: stops allow flights, so we run exactly rounds.
With updates in place, dist[v] can be smaller than that length, because one round can extend a path by several edges, as round 1 did on the courier map. To make a round add one flight and no more, we copy the array before the round and read only from the copy:
INF = float("inf")
def cheapest_price(n, flights, src, dst, k):
cost = [INF] * n
cost[src] = 0
for _ in range(k + 1): # k stops allow k + 1 flights
previous = cost[:] # the costs before this round
for a, b, price in flights:
if previous[a] + price < cost[b]:
cost[b] = previous[a] + price
return -1 if cost[dst] == INF else cost[dst]
print(cheapest_price(4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1))
print(cheapest_price(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1))
print(cheapest_price(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0))The last three lines run the official samples.
| After | Flights allowed | Reading the copy | Updating in place |
|---|---|---|---|
| The start | none | [0, ∞, ∞, ∞] | [0, ∞, ∞, ∞] |
| Round 1 | at most 1 | [0, 100, ∞, ∞] | [0, 100, 200, 400] |
| Round 2 | at most 2 | [0, 100, 200, 700] | [0, 100, 200, 400] |
With the copy, round 1 can only use flights that leave city 0, and after two rounds the price of city 3 is 700. Updating in place lets round 1 take the flights 0 → 1, 1 → 2 and 2 → 3 one after another, and the route with three flights slips in at 400.
There are at most 100 rounds and 4,950 flights, which makes 495,000 relaxations, and a route costs at most , which fits in an int.
Step through the rounds
The widget relaxes one edge at a time. It opens on the map of this page. The example Cheapest Flights, k = 1 runs the first sample, and the switch above the distances chooses between reading the copy and updating in place, so both columns of the table can be replayed. The last example is a graph of four vertices with a negative cycle, where one more pass after the last round still lowers a vertex.
Largest totals with negated weights
Bellman-Ford can also find the path with the largest total, because the largest total becomes the smallest one when every weight is negated. The next problem asks for that, and adds the case where a cycle makes the total as large as we like.
A game has rooms and one-way tunnels. Each tunnel changes your score by , which may be negative, and you may use a tunnel many times. Start in room 1 with score 0 and walk to room .
The first line has and , and each tunnel is given as , and . Room can be reached from room 1. Print the largest possible score, or -1 if the score can be made arbitrarily large.
Constraints
Sample · Input
4 5 1 2 3 2 4 -1 1 3 -2 3 4 7 1 4 4
Output
5
In the sample the best route is 1, 3, 4, with a score of .
We give the tunnel from to the weight . The largest score at a room is then minus its distance from room 1, and a loop of tunnels that raises the score is a negative cycle. The answer is when such a cycle can be used on the way to room . For that, the cycle must be reachable from room 1, and room must be reachable from the cycle. A loop from which room cannot be reached does not change the answer.
So the program runs rounds and then round . If round lowers the distance of a room , then can be reached from a loop that raises the score, and the score is unbounded if room can be reached from . The rooms from which room can be reached are found beforehand, by a breadth-first search from room along the tunnels in reverse.
INF = float("inf")
def high_score(n, tunnels):
dist = [INF] * (n + 1) # dist[v] is minus the best score at room v
dist[1] = 0
for _ in range(n - 1):
for a, b, x in tunnels:
if dist[a] - x < dist[b]:
dist[b] = dist[a] - x
reaches_end = [False] * (n + 1) # rooms from which room n can be reached
reaches_end[n] = True
backward = [[] for _ in range(n + 1)]
for a, b, _ in tunnels:
backward[b].append(a)
queue = deque([n])
while queue:
v = queue.popleft()
for u in backward[v]:
if not reaches_end[u]:
reaches_end[u] = True
queue.append(u)
for a, b, x in tunnels: # round n
if dist[a] - x < dist[b] and reaches_end[b]:
return -1
return -dist[n]
data = list(map(int, sys.stdin.buffer.read().split()))
n, m = data[0], data[1]
tunnels = [data[2 + 3 * i : 5 + 3 * i] for i in range(m)]
print(high_score(n, tunnels))On the sample input the program prints 5.
For the largest input the rounds make relaxations.
Cost of Bellman-Ford
- Bellman-Ford
time - At most rounds of relaxations, and one more round to look for a negative cycle. High Score needs about relaxations.
- With at most $k$ edges on a path
time - rounds that each copy distances and relax edges: at most 495,000 relaxations for Cheapest Flights.
- Memory
- The list of edges, the distances and, for the limit on edges, one copy of them.
Common mistakes with Bellman-Ford
Updating the prices of Cheapest Flights in place during a round.
- Where it breaks
- On the first sample with
k = 1the program returns 400, the price of a route with two stops. The answer is 700. - The fix
- Read every price in a round from the copy taken before the round.
Answering -1 in High Score whenever round lowers any room.
- Where it breaks
- For
n = 3and the tunnels[[1, 3, 5], [1, 2, 1], [2, 2, 1]], the loop at room 2 keeps raising the score of room 2, and the program prints -1. Room 2 has no tunnel to room 3, and the answer is 5. - The fix
- Only a room from which room can be reached makes the answer unbounded.
Giving an undirected edge a negative weight.
- Where it breaks
- With a single two-way road of weight between towns 0 and 1, stored as the two edges
0 → 1and1 → 0, every round lowers both towns, and round 2 reports a negative cycle. - The fix
- Stored as two directed edges, such a road is a cycle of weight , so a graph that has one has no shortest paths. Use Bellman-Ford for negative weights on directed edges only.
Recall A graph has 5 vertices and no negative cycle. How many rounds can Bellman-Ford need before every distance is final, and when can it stop sooner?
At most 4. A shortest path to each vertex visits no vertex twice, so it has at most edges, and after round every vertex whose shortest path has at most edges is final. The algorithm can stop after the first round that changes nothing, because every later round would read the same distances and change nothing either.