BFS finds shortest paths only when every edge costs the same. The moment edges carry different weights, swap the queue for a heap. That one change is Dijkstra.
Breadth-first search works because it reaches nodes in order of hop count, and with equal edges hop count is distance. Give the edges weights and that breaks: two cheap hops can beat one expensive hop. This page covers the three tools that fix it, and when to reach for each: Dijkstra for non-negative weights, 0-1 BFS when every weight is 0 or 1, and Bellman-Ford for negative weights or a cap on the number of edges.
max in place of +.Reading the figure. The left graph has one heavy edge, the red 5, and three edges of cost 1. The middle column is BFS order. It reaches A in one hop and reports 5, which is wrong. The right column is the heap in pop order. Green rows settle a node for good. The red row is the old entry for A. It pops last and the stale check skips it.
Lazy deletion. Python’s heapq has no “decrease key”. When a node’s distance improves, push a second entry and leave the old one in the heap. When an entry comes off, compare it to the best distance on record. If it is larger, it is stale: skip it. The heap grows to O(E) entries, which costs only a constant factor, since log E ≤ 2 log V.
Why negative edges break it. Dijkstra finalises a node on pop. A negative edge found later could make that node cheaper, and the algorithm never looks back. Bellman-Ford does look back: it relaxes every edge, round after round. After round i it knows every shortest path that uses at most i edges. That round count is also what makes it the right tool for “at most k stops”.
import heapq
def dijkstra(graph: dict[int, list[tuple[int, int]]], source: int) -> dict[int, int]:
"""Shortest distance from source to every reachable node.
Args:
graph: Maps each node to a list of (neighbor, weight). Weights are >= 0.
source: The start node.
Returns:
A dict of node to shortest distance, for reachable nodes only.
Example:
>>> g = {0: [(1, 4), (2, 1)], 2: [(1, 2)], 1: []}
>>> sorted(dijkstra(g, 0).items())
[(0, 0), (1, 3), (2, 1)]
"""
# dist holds the best distance found so far. The source costs 0 to reach.
dist = {source: 0}
# Heap entries are (distance, node) so the smallest distance pops first.
# The source starts at distance 0.
heap = [(0, source)]
# Invariant: when an entry pops and is not stale, its distance is final.
while heap:
d, node = heapq.heappop(heap) # cheapest tentative node left
if d > dist[node]: # stale: a cheaper entry already won
continue
# Relax: try to improve each neighbor by going through node.
for neighbor, weight in graph.get(node, []): # []: node with no edges
candidate = d + weight # cost to reach neighbor via node
# inf: a node we have never reached counts as infinitely far.
if candidate < dist.get(neighbor, float("inf")):
dist[neighbor] = candidate
# Push a new entry. The old one stays and is skipped later.
heapq.heappush(heap, (candidate, neighbor))
return dist
The stale check d > dist[node] is the whole of lazy deletion. Without it the code is still correct, but it re-relaxes edges from old entries and can blow up to far more work. An equivalent form keeps a done set and skips any node already in it.
Reading the figure. Each column is one pop, using the docstring graph. The amber box is the entry just popped. Blue boxes are live heap entries. A red entry is stale: dist already holds a smaller value for that node. Notice that (4, 1) turns red in step 2 but stays in the heap. Lazy deletion only drops it in step 4.
from collections import deque
def zero_one_bfs(
graph: dict[int, list[tuple[int, int]]], source: int
) -> dict[int, int]:
"""Shortest distances when every edge weight is 0 or 1.
Args:
graph: Maps each node to a list of (neighbor, weight), weight in {0, 1}.
source: The start node.
Returns:
A dict of node to shortest distance, for reachable nodes only.
Example:
>>> g = {0: [(1, 1), (2, 0)], 2: [(1, 0)], 1: []}
>>> sorted(zero_one_bfs(g, 0).items())
[(0, 0), (1, 0), (2, 0)]
"""
dist = {source: 0} # the source costs 0 to reach
queue = deque([source])
# Invariant: the deque holds at most two distances, d at the front and
# d + 1 at the back, in that order. So the front is always a cheapest node.
while queue:
node = queue.popleft() # popleft: take a cheapest node
for neighbor, weight in graph.get(node, []): # []: node with no edges
candidate = dist[node] + weight
# inf: a node we have never reached counts as infinitely far.
if candidate < dist.get(neighbor, float("inf")):
dist[neighbor] = candidate
if weight == 0: # 0: same distance as node, so it goes first
queue.appendleft(neighbor)
else: # weight 1: one more, so it waits its turn
queue.append(neighbor)
return dist
The deque plays the part of the heap. A free edge goes to the front, a paid edge to the back, so the deque stays sorted with no log factor. A node can be pushed twice if it improves. Re-processing it is harmless because a second pass finds nothing better. The classic use is LeetCode 1368, Minimum Cost to Make at Least One Valid Path in a Grid: following the arrow costs 0, changing it costs 1.
Reading the figure. Each row is one step on the docstring graph. Blue cells are queued nodes, front on the left. The red cell is an old copy of node 1, pushed when its distance was still 1. Notice that node 2 and the improved node 1 both enter at the front, because their edges cost 0. The old copy pops last and changes nothing.
def bellman_ford(
n: int, edges: list[tuple[int, int, int]], source: int, max_edges: int
) -> list[float]:
"""Cheapest cost to each node using at most max_edges edges.
Args:
n: Number of nodes, labelled 0 to n - 1.
edges: Directed (start, end, weight) triples. Weights may be negative.
source: The start node.
max_edges: Most edges a path may use. Pass n - 1 for plain shortest paths.
Returns:
A list of costs. Unreachable nodes hold float("inf").
Example:
>>> edges = [(0, 1, 4), (0, 2, 5), (2, 1, -3)]
>>> bellman_ford(3, edges, 0, 1)
[0, 4, 5]
>>> bellman_ford(3, edges, 0, 2)
[0, 2, 5]
"""
# inf: every node starts unreachable. One slot per node, so n slots.
cost = [float("inf")] * n
cost[source] = 0 # the source costs 0 to reach
# Loop variable is unused: each pass is one more allowed edge.
# Invariant: after pass i, cost[v] is the best path with at most i edges.
for _ in range(max_edges):
previous = cost[:] # [:]: a copy, so this pass reads last pass only
for start, end, weight in edges:
# Extend a path from the LAST pass by exactly one edge.
if previous[start] + weight < cost[end]:
cost[end] = previous[start] + weight
return cost
With max_edges = n - 1 this is textbook Bellman-Ford: no simple path has more than n - 1 edges. Run one extra pass after that. If anything still improves, the graph has a negative cycle reachable from the source. When there is no edge limit you may drop the copy, which only speeds things up. With a limit, the copy is required. Problem 3 shows why.
Reading the figure. The graph is the docstring example. The red -3 is the negative edge. Each row is the cost list after one pass. Amber cells changed in that pass. The green cell is the improvement that needs two edges. With max_edges = 1 you stop after round 1 and get 4.
if d > dist[node]: continue, old heap entries re-relax edges with wrong distances. The answer stays right but the work can explode.k + 1 edges. Say it out loud before you code the loop.A network has n nodes labelled 1 to n. times[i] = (u, v, w) means a signal takes w time to travel from u to v. A signal starts at node k. Return the time until every node has it, or -1 if some node never does.
k. Weights are non-negative, so this is Dijkstra.import heapq
from collections import defaultdict
def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
"""Time for a signal from node k to reach every node, or -1.
Args:
times: Directed edges (u, v, w), travel time w >= 0.
n: Number of nodes, labelled 1 to n.
k: The node that sends the signal.
Returns:
The time when the last node hears the signal, or -1 if one never does.
Example:
>>> network_delay_time([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2)
2
>>> network_delay_time([[1, 2, 1]], 2, 2)
-1
"""
# Adjacency list: graph[u] is a list of (v, w). defaultdict gives [] for leaves.
graph: dict[int, list[tuple[int, int]]] = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
final: dict[int, int] = {} # node to its settled shortest time
heap = [(0, k)] # (time, node). The sender hears it at time 0.
# Invariant: every node in final has its true shortest time.
while heap:
time, node = heapq.heappop(heap) # earliest unsettled arrival
if node in final: # stale: this node was settled earlier
continue
final[node] = time # first pop is the shortest time
for neighbor, delay in graph[node]:
if neighbor not in final: # settled nodes cannot improve
heapq.heappush(heap, (time + delay, neighbor))
# Fewer than n settled means some node is unreachable, so -1 per the problem.
return max(final.values()) if len(final) == n else -1
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2:
(0, 2). Settle node 2 at 0. Push (1, 1) and (1, 3).(1, 1). Settle node 1 at 1. No edges out.(1, 3). Settle node 3 at 1. Push (2, 4).(2, 4). Settle node 4 at 2. Heap empty.Reading the figure. Every edge costs 1 here. In each frame the amber node has just popped and settled. Green nodes settled earlier. Blue nodes wait in the heap, and grey nodes are not yet found. The t= label is the settled time. The answer is the largest label once all four are green.
k: len(final) < n, return -1.n = 1: the sender is the only node, answer 0.n + 1 would also work. The dict avoids the question.You are given a grid of heights. You start at the top-left cell and want to reach the bottom-right, 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 minimum effort.
max instead of +.max never makes a route cheaper as it grows, just as adding a non-negative weight never does. That is the only property Dijkstra needs.import heapq
def minimum_effort_path(heights: list[list[int]]) -> int:
"""Smallest possible largest step on a route from top-left to bottom-right.
Args:
heights: A non-empty grid of cell heights.
Returns:
The minimum effort over all routes.
Example:
>>> minimum_effort_path([[1, 2, 2], [3, 8, 2], [5, 3, 5]])
2
>>> minimum_effort_path([[7]])
0
"""
rows, cols = len(heights), len(heights[0]) # [0]: any row gives the width
# best[r][c]: smallest effort found so far to reach (r, c). inf means unseen.
best = [[float("inf")] * cols for _ in range(rows)]
best[0][0] = 0 # the start costs 0 effort: no steps yet
heap = [(0, 0, 0)] # (effort, row, col): the start, effort 0
# Four moves: down, up, right, left. Each is a (row change, col change).
steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
# Invariant: a non-stale pop carries the final effort for its cell.
while heap:
effort, r, c = heapq.heappop(heap)
if effort > best[r][c]: # stale: a better entry already won
continue
# - 1: last row and last column. Final on pop, so return now.
if r == rows - 1 and c == cols - 1:
return effort
for dr, dc in steps:
nr, nc = r + dr, c + dc
# 0 is the first row or column. rows and cols are one past the last.
if 0 <= nr < rows and 0 <= nc < cols:
climb = abs(heights[nr][nc] - heights[r][c])
candidate = max(effort, climb) # route effort is its worst step
if candidate < best[nr][nc]:
best[nr][nc] = candidate
heapq.heappush(heap, (candidate, nr, nc))
# Not reached: the target is always reachable. Kept as a safe fallback.
return best[rows - 1][cols - 1] # - 1: index of the last row and column
heights = [[1,2,2],[3,8,2],[5,3,5]]:
(0, 0, 0). Push right (1, 0, 1) and down (2, 1, 0).(1, 0, 1). Push (1, 0, 2). Also push (6, 1, 1), the climb into the 8.(1, 0, 2). Push (1, 1, 2).(1, 1, 2). Step to (2,2) climbs 3, push (3, 2, 2).(2, 1, 0). Push (2, 2, 0). Pop it, push (2, 2, 1). Pop it, step to (2,2) climbs 2, push (2, 2, 2).(2, 2, 2). Target. Return 2, by the left column and bottom row.Reading the figure. On the left, green cells form the winning route and amber cells form the route along the top. On the right, e= is the effort when the cell pops and # is the pop order. The red cell is the 8. It sits in the heap at effort 6 but the target pops first, so it is never used.
0.0.There are n cities and a list of flights[i] = (from, to, price). Return the cheapest price from src to dst using at most k stops, or -1 if there is no such route.
k stops means at most k + 1 flights. So this is Bellman-Ford with max_edges = k + 1.dst in time.i, cost[city] is the cheapest price using at most i flights.0→1 for 100, 1→2 for 100 and 0→2 for 500, with k = 0, so one flight only. In place, the first edge sets cost[1] = 100. The second edge then reads that fresh 100 and sets cost[2] = 200. That is two flights inside a one-flight round, and the answer 200 is wrong. Reading from previous, a snapshot of the last round, means previous[1] is still infinity, so only the direct 500 counts. The copy is what makes “round i” mean “at most i edges”.def find_cheapest_price(
n: int, flights: list[list[int]], src: int, dst: int, k: int
) -> int:
"""Cheapest price from src to dst with at most k stops, or -1.
Args:
n: Number of cities, labelled 0 to n - 1.
flights: Directed (start, end, price) triples, price >= 0.
src: Departure city.
dst: Arrival city.
k: Most stops allowed between src and dst.
Returns:
The cheapest price, or -1 if no route fits within k stops.
Example:
>>> flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
>>> find_cheapest_price(3, flights, 0, 2, 1)
200
>>> find_cheapest_price(3, flights, 0, 2, 0)
500
"""
# inf: every city starts unreachable. One slot per city, so n slots.
cost = [float("inf")] * n
cost[src] = 0 # being at src costs nothing
# k stops means k + 1 flights, so k + 1 rounds. One flight per round.
# Invariant: after round i, cost[c] is the cheapest price using at most i flights.
for _ in range(k + 1):
previous = cost[:] # [:]: snapshot of last round, read-only here
for start, end, price in flights:
# Read from previous, write to cost: one new flight per round, no more.
if previous[start] + price < cost[end]:
cost[end] = previous[start] + price
# Still inf means no route within k + 1 flights, so -1 per the problem.
return -1 if cost[dst] == float("inf") else cost[dst]
flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1, so 2 rounds:
cost = [0, inf, inf].[0, inf, inf]. Edge 0→1 sets cost[1] = 100. Edge 1→2 reads previous[1] = inf, no change. Edge 0→2 sets cost[2] = 500. Now [0, 100, 500].[0, 100, 500]. Edge 1→2 gives 100 + 100 = 200 < 500, so cost[2] = 200.k = 0 only round 1 runs and the answer is 500.Reading the figure. Each row is cost after one round. Amber cells changed in that round. The green 200 is the answer for k = 1. The red row shows the bug from the box above. Without the copy, a single round chains two flights.
src == dst: price 0, from the start state.-1.(city, flights used). Worth naming, but Bellman-Ford is shorter and easier to prove.An n × n grid holds distinct elevations. At time t the water is at level t, and you can move between neighbouring cells only if both are at most t. Moving takes no time. Starting at the top-left, return the earliest time you can reach the bottom-right.
t exactly when its highest cell is at most t. So the answer is the route that minimises its highest cell.max.visited set gives lazy deletion with no distance table.import heapq
def swim_in_water(grid: list[list[int]]) -> int:
"""Earliest time to swim from the top-left to the bottom-right cell.
Args:
grid: An n by n grid of distinct elevations, n >= 1.
Returns:
The smallest water level that connects the two corners.
Example:
>>> swim_in_water([[0, 2], [1, 3]])
3
>>> swim_in_water([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5],
... [12, 13, 14, 15, 16], [11, 17, 18, 19, 20],
... [10, 9, 8, 7, 6]])
16
"""
n = len(grid)
target = (n - 1, n - 1) # n - 1: the last row and last column
# (level, row, col). The start needs water at least as high as its own cell.
heap = [(grid[0][0], 0, 0)]
visited: set[tuple[int, int]] = set()
# Four moves: down, up, right, left. Each is a (row change, col change).
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
# Invariant: a cell's first pop carries the lowest level that reaches it.
while heap:
level, r, c = heapq.heappop(heap)
if (r, c) in visited: # stale: settled by an earlier pop
continue
visited.add((r, c))
if (r, c) == target: # final on pop, so this is the answer
return level
for dr, dc in moves:
nr, nc = r + dr, c + dc
# 0 is the first row or column. n is one past the last.
if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
# The route now needs water up to its highest cell so far.
heapq.heappush(heap, (max(level, grid[nr][nc]), nr, nc))
return -1 # -1: not reached, the grid is connected
grid = [[0, 2], [1, 3]]:
(0, 0, 0). Push down (1, 1, 0) and right (2, 0, 1).(1, 1, 0). Push (3, 1, 1), since the target cell is 3.(2, 0, 1). Its neighbour (1,1) would also give 3. Push it again.(3, 1, 1). Target. Return 3. The second copy is never used.Reading the figure. Each heap entry is (level, row, col). The amber cell has just popped. Green cells are settled, blue cells wait in the heap, and grey cells are not yet reached. Notice the target is pushed twice at level 3. The first pop wins and the copy is never read.
n = 1: answer is grid[0][0], returned on the first pop.max(grid[0][0], grid[n-1][n-1]). Both corners must be under water.0..n²-1, so binary search on t with a BFS check is a fine alternative, at O(n² log n) too.if d > dist[node]: continue.Dijkstra keeps the best candidate at the front of a heap. Pattern 22, the Monotonic Deque, keeps the best candidate at the front of a deque instead, for when the candidates live in a sliding window and expire in order.