Dijkstra's algorithm
Relaxing every edge in rounds finds the distances, but it relaxes the same edge many times, and most of those relaxations change nothing. Dijkstra's algorithm relaxes each edge at most once. It deals with the vertices in order of their distance from the source, so that by the time it relaxes the edges leaving a vertex, the distance of that vertex is final. It requires that no weight is negative, which holds for times, lengths and prices, as in this problem:
A network has nodes labelled 1 to . Each entry times[i] = [u, v, w] is a one-way link: a signal sent from u reaches v after w time units.
A signal leaves node k. Return the time it takes until every node has received it, or -1 if some node never does.
Constraints
-
times.length - and
- No link appears twice
Sample 1 · Input
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output
2
Sample 2 · Input
times = [[1,2,1]], n = 2, k = 1
Output
1
Sample 3 · Input
times = [[1,2,1]], n = 2, k = 2
Output
-1
In the first sample the signal starts at node 2. Nodes 1 and 3 receive it after 1 unit of time, and node 3 passes it on to node 4, which receives it at time . In the third sample node 2 has no link going out, so node 1 never receives the signal and the answer is .
The links are the edges of a directed weighted graph, and the signal travels along all of them at once, so a node receives it at a time equal to its distance from node . The last node to receive it is the one with the largest distance. The answer is therefore the largest of the distances from , or if one of them is infinite.
To find the distances, the algorithm marks a vertex as settled once its distance is final. It works as follows:
- Set
distto 0 for the source and to for every other vertex. No vertex is settled. - Among the vertices that are not settled, pick the one with the smallest tentative distance.
- Mark that vertex as settled, and relax every edge that leaves it.
- Repeat steps 2 and 3 until every vertex is settled, or until all the vertices that are left are at .
The vertices that are still at at the end cannot be reached from the source.
The algorithm on the courier map
The samples of the problem are too small to show much, so we run the algorithm on the courier map of the first page, with town 0 as the source:
Town 0 is settled first, at distance 0. Its two roads give town 1 the tentative distance 4 and town 2 the tentative distance 1. Of the towns that are not settled, town 2 is now the closest, so it comes next. Its road to town 1 offers , which lowers town 1 from 4 to 3, and its road to town 3 gives town 3 the distance . Town 1 is next, at 3, and its road lowers town 3 to . Town 3 is settled last and has no roads. Town 4 is still at , so the algorithm stops.
dist after each step. The highlighted towns are settled.Each of the five roads was relaxed once, while the rounds of the first page needed 20 relaxations. Town 1 was given the distance 4 at first and was settled later, at 3, when it had become the closest town that was left. A vertex is settled at that moment, and not when it first gets a distance.
Why a settled distance is final
For the algorithm to be correct, the following has to hold: when a vertex is picked in step 2, its tentative distance is already its true distance. It holds whenever no weight is negative.
Suppose it has been true for every vertex settled so far, so that the settled vertices all have their true distances. Let the vertex that is picked now be , with tentative distance , and take any path from the source to . The path starts at the source, which is settled, and ends at , which is not, so somewhere it leaves the settled vertices for the first time. Let be the edge where that happens, with settled and not.
Since is settled, dist[u] is the true distance of , so it is at most the length of the part of the path up to . The edge was relaxed when was settled, so dist[x] is at most dist[u] plus the weight of that edge, which is at most the length of the path up to . The rest of the path, from to , is made of edges with weights of 0 or more, so it cannot make the path any shorter. And was picked because its tentative distance is the smallest among the vertices that are not settled, so is at most dist[x]. Put together,
Every path to has length at least , and is the length of a path that exists, so is the distance of .
A negative weight on the courier map
The argument used the fact that no weight is negative in one place: the part of the path after could not make it shorter. With a negative weight it can. Add two roads to the courier map, 0 → 4 taking 6 minutes and 4 → 1 taking . The algorithm settles town 0, then town 2 at 1, town 1 at 3, town 3 at 4, and finally town 4 at 6.
Only then is the road 4 → 1 relaxed. It offers town 1 a path of length , which is less than 3, and dist[1] is lowered to 2. But town 1 is already settled, so its road to town 3, which was relaxed with the old distance, is not relaxed again. Town 3 keeps the distance 4, while the path 0 → 4 → 1 → 3 has length .
In the widget you choose which town to settle. It accepts only a town with the smallest tentative distance, and says why when another one is chosen. The button above the map adds the two roads, and the same run then ends with the wrong distance for town 3. Graphs with negative weights are the subject of the next page.
Find the closest vertex with a heap
Step 2 needs the vertex with the smallest tentative distance among those that are not settled. The plain way to find it is to scan all the vertices, which takes steps each time and steps over the whole run: for vertices. A min-heap does better. We keep pairs (distance, vertex) in it, and it hands over the pair with the smallest distance in a number of steps that is about the logarithm of its size.
The heaps that come with Python and C++ cannot lower the distance of a pair that is already inside them, an operation that textbooks call decrease-key, and tentative distances do go down. So whenever a relaxation lowers dist[v], we push a new pair with the new distance and leave the old pair where it is. A vertex can then have several pairs in the heap. The one with the smallest distance comes out first, and at that moment the vertex is settled. Its other pairs come out later and are stale. We recognise a stale pair because its vertex is already settled, and we skip it.
| Pair popped | What happens | Heap afterwards |
|---|---|---|
| none yet | The source is pushed. | (0, 0) |
| (0, 0) | Town 0 is settled. Push (4, 1) and (1, 2). | (1, 2) (4, 1) |
| (1, 2) | Town 2 is settled. Push (3, 1) and (6, 3). | (3, 1) (4, 1) (6, 3) |
| (3, 1) | Town 1 is settled. Push (4, 3). | (4, 1) (4, 3) (6, 3) |
| (4, 1) | Stale: town 1 is already settled. | (4, 3) (6, 3) |
| (4, 3) | Town 3 is settled. It has no roads. | (6, 3) |
| (6, 3) | Stale: town 3 is already settled. | empty |
The skip also matters for speed. A stale pair that is not skipped relaxes all the edges of its vertex a second time, and in a large graph that can cost more than the rest of the run.
Picture a source with a road to each of 50,000 towns, a road from each of those towns to one hub, and roads from the hub to 50,000 further towns. The graph has 150,000 edges. Say the road from the source to town has weight , and the road from town to the hub has weight . Town is settled at distance and offers the hub the distance , which is 1 less than the offer before it, so the hub is pushed 50,000 times.
Every town is settled at a distance of at most 50,000 and every offer to the hub is at least 50,000, so all of these pairs are in the heap before the hub is settled. With the skip, the roads that leave the hub are relaxed once. Without it they are relaxed once for each pair of the hub:
Dijkstra's algorithm in code
The function dijkstra takes the adjacency lists of a graph, with pairs (neighbor, weight) as on the first page, and returns the distance of every vertex from source. network_delay_time builds the lists from the links and returns the largest distance.
INF = float("inf")
def dijkstra(graph, source):
dist = [INF] * len(graph)
settled = [False] * len(graph)
dist[source] = 0
heap = [(0, source)] # pairs (distance, vertex)
while heap:
d, u = heapq.heappop(heap)
if settled[u]:
continue # a stale pair
settled[u] = True
for v, w in graph[u]:
if d + w < dist[v]: # relax the edge u -> v
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
return dist
def network_delay_time(times, n, k):
graph = [[] for _ in range(n + 1)] # nodes are numbered from 1
for u, v, w in times:
graph[u].append((v, w))
latest = max(dijkstra(graph, k)[1:])
return -1 if latest == INF else latest
print(network_delay_time([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))
print(network_delay_time([[1, 2, 1]], 2, 1))
print(network_delay_time([[1, 2, 1]], 2, 2))
courier = [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], [], []]
print(dijkstra(courier, 0))The first three prints run the official samples, and the last one runs the courier map.
A pair in the heap has the distance first. Pairs are compared by their first field, and by the second only when the first fields are equal, so the heap orders them by distance, which is the order step 2 needs.
The loop takes the smallest pair and skips it if its vertex is already settled. Otherwise it settles the vertex and relaxes its edges with the distance d from the pair. A new pair is pushed only when a relaxation lowers a distance, so each edge adds at most one pair to the heap.
The nodes of this problem are numbered from 1, so the lists have entries, entry 0 stays empty, and the largest distance is taken over the entries from 1 on.
Python's float("inf") is larger than every number, so it can stand for in the comparisons and in max.
Worked example
Step through the heap
The trace runs the same code on the courier map and shows the heap after every pop and every relaxation. In its second example three roads of 1 minute beat one road of 10, and in the third a road leads into town 0 and is never used.
Town 0 starts at distance 0. Every other town is unreached.
- heap
- (0, 0)
Change the example input
Current result: [0,3,1,4,-1]
Cost of Dijkstra's algorithm
- With a heap
time - Every edge is relaxed once and pushes at most one pair, so at most pairs go through the heap, and each push or pop takes about steps. For vertices and edges that is about steps.
- With a scan in place of the heap
time - picks that each look at all tentative distances, and one relaxation for each edge.
- Memory
- The adjacency lists,
dist, the settled marks and up to pairs in the heap.
The scan is the better choice when the graph is dense, which means that it has close to edges. With 1,000 towns and a road between every ordered pair of them, is 999,000. The heap version then takes about steps, and the scan about .
Paths measured by their largest step
Dijkstra's algorithm does not need the length of a path to be a sum. The next problem measures a path by its largest edge:
You get a grid heights of cell heights. Start at the top-left cell and reach the bottom-right cell, moving up, down, left or right. The effort of a route is the largest absolute height difference between two consecutive cells on it.
Return the smallest effort of any route.
Constraints
- rows, columns
-
heights[i][j]
Sample 1 · Input
heights = [[1,2,2],[3,8,2],[5,3,5]]
Output
2
Sample 2 · Input
heights = [[1,2,3],[3,8,4],[5,3,5]]
Output
1
Sample 3 · Input
heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output
0
In the first sample the route over the heights 1, 3, 5, 3, 5 changes height by exactly 2 at every step, so its effort is 2. No route does better: the corner cell has height 5 and its two neighbors have heights 2 and 3, so the last step alone changes the height by at least 2.
The cells are the vertices, and a move between two neighboring cells is an edge whose weight is the difference of their heights. The effort of a path is the largest weight on it. When a path with effort is extended by an edge of weight , its effort becomes , while a length would have become . That is the only change the algorithm needs: an edge lowers effort[v] when is smaller.
The argument for settling the closest vertex carries over with in place of . The effort of a path up to is still at least effort[x], and the rest of the path cannot lower it, because is never smaller than .
INF = float("inf")
def minimum_effort(heights):
rows, cols = len(heights), len(heights[0])
effort = [[INF] * cols for _ in range(rows)]
settled = [[False] * cols for _ in range(rows)]
effort[0][0] = 0
heap = [(0, 0, 0)] # (effort, row, column)
while heap:
e, r, c = heapq.heappop(heap)
if settled[r][c]:
continue
settled[r][c] = True
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 = abs(heights[nr][nc] - heights[r][c])
if max(e, w) < effort[nr][nc]: # max in place of +
effort[nr][nc] = max(e, w)
heapq.heappush(heap, (effort[nr][nc], nr, nc))
return effort[rows - 1][cols - 1]
print(minimum_effort([[1, 2, 2], [3, 8, 2], [5, 3, 5]]))
print(minimum_effort([[1, 2, 3], [3, 8, 4], [5, 3, 5]]))
print(minimum_effort([[1, 2, 1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 1, 1, 2, 1]]))The last three lines run the official samples.
As in a BFS on a grid, the program builds no adjacency lists and works out the neighbors of a cell when it takes the cell from the heap. A grid has 10,000 cells and fewer than 40,000 moves, so at most 40,000 triples go through the heap.
Vertices that carry a state
In the next problem the city we are in is not enough to tell how a trip can go on:
There are cities and one-way flights, each with a price. Travel from city 1 to city as cheaply as possible. You have one coupon that halves the price of a single flight, rounded down.
The first line has and , and each of the next lines has , and : a flight from city to city costing . A route from city 1 to city always exists. Print the cheapest total price.
Constraints
Sample · Input
3 4 1 2 3 2 3 1 1 3 7 2 1 5
Output
2
In the sample the cheapest trip takes the flight from city 1 to city 2 with the coupon, for , and then the flight from city 2 to city 3 for 1, which makes 2.
What the rest of a trip costs depends on the city we are in and also on whether the coupon is still unused. So we make a vertex of every state, as a breadth-first search over the positions of a puzzle does: a state is a city together with whether the coupon has been used yet. Every city becomes two vertices, and a flight from to with price becomes three edges:
A path in this graph is a trip together with a choice of the flight on which the coupon is spent. The answer is the distance from city 1 with the coupon unused to city with the coupon used. Arriving with the coupon unused is never cheaper, since halving the price of a flight never raises it.
The program numbers city with the coupon unused as vertex , and with the coupon used as vertex . On this graph it runs Dijkstra's algorithm unchanged:
INF = float("inf")
def flight_discount(n, flights):
# City c is vertex c before the coupon is used and vertex c + n after.
graph = [[] for _ in range(2 * n + 1)]
for a, b, price in flights:
graph[a].append((b, price))
graph[a].append((b + n, price // 2)) # this flight uses the coupon
graph[a + n].append((b + n, price))
dist = [INF] * (2 * n + 1)
settled = [False] * (2 * n + 1)
dist[1] = 0
heap = [(0, 1)]
while heap:
d, u = heapq.heappop(heap)
if settled[u]:
continue
settled[u] = True
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
return dist[2 * n]
data = list(map(int, sys.stdin.buffer.read().split()))
n, m = data[0], data[1]
flights = [data[2 + 3 * i : 5 + 3 * i] for i in range(m)]
print(flight_discount(n, flights))On the sample input the program prints 2.
The new graph has vertices and edges, at most and , so the run takes about three times the work of a run on the flights alone.
Count the shortest paths
Dijkstra's algorithm can also count the shortest paths while it runs:
There are cities and one-way flights with prices. For routes from city 1 to city , print four numbers: the minimum price, how many routes have that price (modulo ), and the fewest and the most flights on a minimum-price route.
The input is laid out as in Flight Discount, and a route from city 1 to city always exists.
Constraints
Sample · Input
4 5 1 4 5 1 2 4 2 4 5 1 3 2 3 4 3
Output
5 2 1 2
In the sample two routes have the minimum price 5: the direct flight from city 1 to city 4, and the route 1, 3, 4 at . They use 1 and 2 flights, so the output is 5 2 1 2.
In a graph without cycles, the routes to every vertex can be counted in an array ways. The count of a vertex is the sum of the counts of the vertices with an edge into it, and taking the vertices in topological order makes those counts final before they are used. The same idea works here with two changes: only flights that lie on a cheapest route are counted, and the order is the one in which Dijkstra's algorithm settles the cities.
A flight with price is the last flight of a cheapest route to exactly when dist[u] + w equals dist[v]. So when a city is settled and its flights are relaxed, each flight falls into one of three cases. If dist[u] + w is smaller than dist[v], every route counted for so far was too expensive: dist[v] is lowered and ways[v] starts again from ways[u]. If the two are equal, the cheapest routes through join the ones already counted, and ways[u] is added to ways[v]. If it is larger, nothing changes. The fewest and the most flights are kept in the same way, with fewest[u] + 1 and most[u] + 1 in place of ways[u], and with min and max in place of the sum.
INF = float("inf")
MOD = 10**9 + 7
def investigation(n, flights):
graph = [[] for _ in range(n + 1)]
for a, b, price in flights:
graph[a].append((b, price))
dist = [INF] * (n + 1)
ways = [0] * (n + 1) # number of cheapest routes
fewest = [0] * (n + 1) # fewest flights on a cheapest route
most = [0] * (n + 1) # most flights on a cheapest route
settled = [False] * (n + 1)
dist[1], ways[1] = 0, 1
heap = [(0, 1)]
while heap:
d, u = heapq.heappop(heap)
if settled[u]:
continue
settled[u] = True
for v, w in graph[u]:
if d + w < dist[v]: # cheaper: forget the old routes to v
dist[v] = d + w
ways[v] = ways[u]
fewest[v] = fewest[u] + 1
most[v] = most[u] + 1
heapq.heappush(heap, (dist[v], v))
elif d + w == dist[v]: # a tie: add the routes through u
ways[v] = (ways[v] + ways[u]) % MOD
fewest[v] = min(fewest[v], fewest[u] + 1)
most[v] = max(most[v], most[u] + 1)
return dist[n], ways[n], fewest[n], most[n]
data = list(map(int, sys.stdin.buffer.read().split()))
n, m = data[0], data[1]
flights = [data[2 + 3 * i : 5 + 3 * i] for i in range(m)]
print(*investigation(n, flights))On the sample input the program prints 5 2 1 2.
When ways[u] is read, it has to be final, and it is, because every price is at least 1. The city before on a cheapest route is strictly closer to city 1 than is, so it was settled earlier and has already added its count. With a flight of price 0 between two cities at the same distance, the heap could settle the second city before the first, and the count would come out too small.
Common mistakes with Dijkstra's algorithm
Marking a vertex as settled when it is pushed, the way BFS marks a vertex when it joins the queue.
- Where it breaks
- On the courier map town 1 is fixed at 4 as soon as town 0 pushes it, and the path through town 2 is ignored. The result is
[0, 4, 1, 6, inf]where it should be[0, 3, 1, 4, inf]. - The fix
- Settle a vertex when its pair is popped. Until then its distance can still go down.
Storing distances in a 32-bit
intin C++.- Where it breaks
- In Flight Discount a route of flights at each costs , far past the
intlimit of about , so the sum overflows and a wrong number is printed. - The fix
- Keep distances in
long long. Python integers do not overflow.
Recall Run Dijkstra's algorithm from vertex 0 on the edges `0 → 1` with weight 10, `0 → 2` with weight 1, `2 → 3` with weight 1 and `3 → 1` with weight 1. In which order are the vertices settled, and which pair is stale?
Vertex 0 is settled at 0 and pushes (10, 1) and (1, 2). Vertex 2 is settled at 1 and pushes (2, 3). Vertex 3 is settled at 2 and pushes (3, 1), because is less than 10. Vertex 1 is settled at 3. The pair (10, 1) is still in the heap. It comes out last and is stale. The distances are 0, 3, 1 and 2.