From here to there
An ambulance dispatcher in São Paulo needs the fastest route from the nearest station to a caller, with travel times that change through the day. Inside the internet, routers running the OSPF protocol each compute the shortest paths from themselves to every other router in their network, and recompute them within seconds when a link fails. A currency trader asks whether converting rupees to yen to euros and back to rupees could ever end with more rupees than she started with. A game engine moves a hundred characters across a map every frame without any of them walking into a wall.
All of these are shortest-path problems on weighted graphs. In Graphs, breadth-first search found paths with the fewest edges. Now edges have weights (kilometres, seconds, money, risk), and we want paths of least total weight. This lesson develops the four classical algorithms, each suited to a different situation:
| Algorithm | Problem | Weights | Time |
|---|---|---|---|
| Dijkstra | one source to all | non-negative | with a binary heap |
| Bellman–Ford | one source to all | any; detects negative cycles | |
| Floyd–Warshall | all pairs | any; detects negative cycles | |
| A* | one source to one target | non-negative, plus a heuristic | often far less than Dijkstra |
Then we look at how real routing engines answer queries on continental road networks in milliseconds, which needs one more idea: preprocessing.
Definitions
Definition— path weight and distance
In a directed graph with edge weights , the weight of a path is the sum of its edge weights. The distance is the least weight of any path from to ; it is if there is no path. A shortest path is a path achieving it. (Undirected graphs are handled by replacing each edge with two directed ones.)
Definition— negative cycle
A negative cycle is a cycle whose total weight is negative. If one can be reached from and can reach , then going round it again and again makes paths to arbitrarily light, and is undefined (or ).
Definition— relaxation
Shortest-path algorithms keep an estimate for each vertex, initially and otherwise. Relaxing an edge means: if , set and .
The common core: relaxation
Three simple facts underlie every algorithm in this lesson.
- Subpaths of shortest paths are shortest paths. If the best route from to passes through , its first part is a best route from to ; otherwise we could swap in a better first part and improve the whole. This is the optimal substructure of dynamic programming.
- Triangle inequality. For every edge : , since one way to reach is to reach optimally and then take the edge.
- Estimates never undershoot. Throughout any sequence of relaxations, , because is always either or the weight of an actual path (the one traced by the parent pointers). And once , it never changes again.
So an algorithm is correct if it relaxes the right edges in a good enough order that every comes down to . The algorithms differ only in which edges they relax and in what order: Bellman–Ford relaxes everything repeatedly; Dijkstra relaxes each edge once, in a cleverly chosen order.
Dijkstra's algorithm
Edsger Dijkstra designed his algorithm in 1956, reportedly in about twenty minutes while sitting at a café terrace in Amsterdam with his fiancée, to demonstrate a new computer on a problem anyone could understand (a road map of the Netherlands). The idea is BFS with a priority queue in place of the plain queue: always settle the closest vertex not yet settled.
Dijkstra(G, s):
d[s] = 0, d[v] = infinity for every other v
put (0, s) in a min-heap
while the heap is not empty:
pop (du, u) with the smallest du
if u is already settled: continue (a stale entry: lazy deletion)
settle u
for each edge (u, v) with weight w:
if du + w < d[v]: d[v] = du + w, parent[v] = u, push (d[v], v)Theorem— Dijkstra is correct for non-negative weights
If every edge weight is non-negative, then when a vertex is settled, . Consequently Dijkstra's algorithm computes all distances from , and the parent pointers form a tree of shortest paths. With a binary heap and lazy deletion it runs in time.
Proof
Suppose not, and let be the first vertex settled with (so , and is reachable). Take a shortest path from to , and let be the first vertex on it that is not yet settled at the moment is popped; let be the vertex before on the path. Then is settled, and since it was settled before , ; when was settled, the edge was relaxed, so
The equality uses fact 1 (the path up to is shortest); the next inequality uses non-negative weights (the rest of the path from to cannot have negative weight). So sits in the heap with a smaller key than , and the heap would have popped before . Contradiction.
Each vertex is settled once, and each edge relaxed once, when its tail is settled. Each relaxation pushes at most one heap entry, so the heap holds at most entries, and every push and pop costs (since ).
∎
Why negative edges break it. The proof's key step is that extending a path never makes it lighter. Take edges of weight 2, of weight 3, of weight and of weight 1. Dijkstra settles at distance 2 and, through it, gives distance 3; only then does it settle and find the lighter route to , of weight . But is already settled, so its edges are never relaxed again, and keeps the wrong distance 3 instead of 2. The error spreads to everything reached from .
import heapq
def dijkstra(graph, s):
"""graph: dict u -> list of (v, weight), weights >= 0. Returns (dist, parent)."""
dist, parent, settled = {s: 0}, {s: None}, set()
heap = [(0, s)]
while heap:
du, u = heapq.heappop(heap)
if u in settled:
continue # stale entry: u was settled more cheaply
settled.add(u)
for v, w in graph.get(u, []):
if du + w < dist.get(v, float("inf")):
dist[v], parent[v] = du + w, u
heapq.heappush(heap, (dist[v], v))
return dist, parent
def route(parent, v):
path = []
while v is not None:
path.append(v)
v = parent[v]
return path[::-1]
# Driving times in minutes between towns on an imaginary map (each road works both ways).
roads = [("Kisima", "Pradera", 25), ("Kisima", "Fjellby", 40), ("Pradera", "Fjellby", 10),
("Pradera", "Hanami", 55), ("Fjellby", "Hanami", 30), ("Fjellby", "Oasis", 70),
("Hanami", "Oasis", 15), ("Hanami", "Tidewater", 45), ("Oasis", "Tidewater", 20)]
graph = {}
for a, b, minutes in roads:
graph.setdefault(a, []).append((b, minutes))
graph.setdefault(b, []).append((a, minutes))
dist, parent = dijkstra(graph, "Kisima")
for town in sorted(dist, key=dist.get):
print(f"{town:10} {dist[town]:3} min via {' -> '.join(route(parent, town))}")
tricky = {"s": [("a", 2), ("b", 3)], "b": [("a", -2)], "a": [("c", 1)]}
print("with a negative edge, Dijkstra says d[c] =", dijkstra(tricky, "s")[0]["c"], "but the truth is 2")With a Fibonacci heap the bound improves to (Fredman and Tarjan, 1987), but binary or 4-ary heaps are faster on real road networks. In OSPF (RFC 2328), every router floods the state of its links to the others and then runs Dijkstra on the resulting map of the network.
Bellman–Ford and negative cycles
When some weights are negative (refunds, energy recovered going downhill, or the logarithms of exchange rates below), we need an algorithm that does not settle vertices early. Bellman–Ford (Richard Bellman 1958, Lester Ford 1956, Edward Moore 1959) simply relaxes every edge, in any order, times.
Theorem— Bellman–Ford
After rounds of relaxing all edges, is at most the weight of the lightest path from to that uses at most edges. If no negative cycle is reachable from , then after rounds for every . A negative cycle is reachable from if and only if some edge can still be relaxed in a further, -th round. The running time is .
Proof
The first claim is by induction on : a lightest path with at most edges ending in the edge consists of a path to with at most edges (whose weight is after round by induction) plus , and round relaxes . Without negative cycles, some shortest path to each vertex is simple (repeating a vertex would include a cycle, of non-negative weight, which can be cut out), so it has at most edges, and after rounds ; with fact 3, equality.
If no negative cycle is reachable, all values are final after rounds, so nothing can be relaxed in round . Conversely, suppose a reachable cycle has negative weight but no edge can be relaxed, so around the cycle. Adding these inequalities, the terms cancel, leaving the cycle's weight, a contradiction.
∎
Bellman–Ford is dynamic programming in disguise: the state is (vertex, number of edges allowed). It is also naturally distributed: each node only needs its neighbours' current estimates. The RIP routing protocol (RFC 2453) is exactly this, with routers periodically telling their neighbours their distance to every destination.
Currency arbitrage. If one rupee buys units of currency , a cycle of exchanges multiplies your money by the product of its rates. Give the edge from to the weight . Then a product greater than 1 corresponds to a sum of logarithms greater than 0, which is a negative cycle. Bellman–Ford finds it.
import math
def bellman_ford(vertices, edges, s):
"""edges: list of (u, v, w). Returns (dist, parent, cycle) where cycle is a negative cycle or None."""
dist = {v: math.inf for v in vertices}
parent = {v: None for v in vertices}
dist[s] = 0
for _ in range(len(vertices) - 1):
changed = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v], parent[v] = dist[u] + w, u
changed = True
if not changed:
break # already final: stop early
for u, v, w in edges: # the extra round
if dist[u] + w < dist[v]:
parent[v] = u
x = v
for _ in range(len(vertices)): # walk back far enough to land on the cycle
x = parent[x]
cycle, y = [x], parent[x]
while y != x:
cycle.append(y)
y = parent[y]
return dist, parent, cycle[::-1]
return dist, parent, None
# Made-up exchange rates: one unit of the first currency buys this many of the second.
rates = {("INR", "JPY"): 1.80, ("JPY", "EUR"): 0.0061, ("EUR", "INR"): 92.0,
("INR", "EUR"): 0.0108, ("EUR", "JPY"): 162.0, ("JPY", "INR"): 0.552}
currencies = sorted({c for pair in rates for c in pair})
edges = [(a, b, -math.log(r)) for (a, b), r in rates.items()]
_, _, cycle = bellman_ford(currencies, edges, "INR")
if cycle:
loop = cycle + cycle[:1]
gain = math.prod(rates[(a, b)] for a, b in zip(loop, loop[1:]))
print("arbitrage:", " -> ".join(loop), f"multiplies money by {gain:.4f}")
else:
print("no arbitrage")All pairs: Floyd–Warshall
Sometimes we need the distance between every pair of vertices: a table of travel times between all the depots of a delivery company, or the input to a clustering algorithm. Running Dijkstra from every vertex costs , which is the right choice for large sparse graphs with non-negative weights. For dense graphs, or graphs with negative edges, the Floyd–Warshall algorithm is simpler.
Number the vertices , and let be the weight of the lightest path from to whose intermediate vertices all lie in . A best such path either avoids vertex , or passes through it exactly once (assuming no negative cycles), splitting into a path and a path that use only intermediates below :
starting from = the edge weights (0 on the diagonal, where there is no edge). That is three nested loops, outermost, over a single matrix updated in place: time and space. A negative entry on the diagonal at the end reveals a negative cycle. With Boolean values in place of numbers the same loops compute which vertices can reach which (Stephen Warshall's transitive closure, 1962). You will implement it in the exercises.
A*: searching towards the goal
Dijkstra from explores outwards in all directions, like a ripple in a pond, settling every vertex closer than the target before reaching it. When there is a single target , most of that work is wasted: to drive from Lyon to Marseille, Dijkstra also settles every town around Lyon in the direction of Paris.
A* (Hart, Nilsson and Raphael, 1968) adds a heuristic , an estimate of the remaining distance from to , and orders the priority queue by : distance so far plus estimated distance to go. Vertices in the direction of the target get priority.
- is admissible if it never overestimates: for every . Then A* returns a shortest path.
- is consistent if for every edge, and . Consistency implies admissibility, and then, like Dijkstra, A* never needs to settle a vertex twice.
The cleanest proof uses reduced weights . Consistency says exactly that . Along any path from to the terms telescope, so every path's reduced weight equals its real weight minus (since ): the same paths are shortest under both weightings. And A* on makes exactly the choices that Dijkstra makes on , which is correct because is non-negative.
Good heuristics come from relaxing the problem. On a road map, the straight-line distance to the target is admissible for distances (no road is shorter than a straight line), and straight-line distance divided by the highest speed limit is admissible for travel times. On a grid where you move in four directions, the Manhattan distance is admissible. With , A* is Dijkstra; the closer is to the true distance, the fewer vertices it explores. Game engines use A* on grids and navigation meshes, and robot planners on maps of free space. Scaling up (weighted A*) explores even less but may return a slightly longer path.
import heapq
def grid_search(grid, start, goal, use_heuristic):
"""Shortest path length on a 4-connected grid ('#' = wall), and the number of cells settled."""
rows, cols = len(grid), len(grid[0])
def h(cell):
return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1]) if use_heuristic else 0
dist, settled = {start: 0}, set()
heap = [(h(start), start)]
while heap:
_, cell = heapq.heappop(heap)
if cell in settled:
continue
settled.add(cell)
if cell == goal:
return dist[cell], len(settled)
r, c = cell
for nxt in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
nr, nc = nxt
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
if dist[cell] + 1 < dist.get(nxt, float("inf")):
dist[nxt] = dist[cell] + 1
heapq.heappush(heap, (dist[nxt] + h(nxt), nxt))
return None, len(settled)
size = 60
grid = [["."] * size for _ in range(size)]
for r in range(5, 55):
grid[r][30] = "#" # a long wall with gaps at both ends
start, goal = (30, 5), (30, 55)
for name, flag in [("Dijkstra", False), ("A* (Manhattan)", True)]:
length, explored = grid_search(grid, start, goal, flag)
print(f"{name:15} path length {length}, cells settled: {explored}")Both find a path of the same length; A* settles far fewer cells, even though the wall forces it to look around.
How routing services answer in milliseconds
A continental road network has tens of millions of intersections. A well-implemented Dijkstra settles millions of them for a long-distance query and takes on the order of a second, and A* with straight-line distances helps less than you might hope: for travel times the estimate must assume the highest possible speed everywhere, which makes it weak. A routing service answering thousands of queries per second needs a different approach: do expensive work once, in advance, so that each query is cheap. The research community, often with industry co-authors, spent the 2000s on this problem, and the survey by Hannah Bast and colleagues (2016) records the outcome: queries on continental networks in well under a millisecond.
Contraction hierarchies (Geisberger, Sanders, Schultes and Delling, 2008) are the most widely used of these ideas, and simple to describe.
- Order the vertices by importance, so that quiet residential corners come first and motorway junctions last. (Heuristics decide the order, for example by how many shortcuts a vertex would need.)
- Contract the vertices one at a time in that order. Contracting removes it from the graph; for every pair of its remaining neighbours and , a small local search looks for a witness, another path from to that is no longer than . If there is none, add a shortcut edge with the weight of . Distances among the remaining vertices are preserved.
- Query with a bidirectional Dijkstra, forwards from and backwards from , in which each search only follows edges (original or shortcut) towards more important vertices. The two searches meet near the top of the hierarchy, after settling only hundreds of vertices instead of millions.
The trade-off is that preprocessing takes minutes and must be redone when weights change, which is awkward for live traffic. Customisable route planning (Delling, Goldberg, Pajor and Werneck, 2011) splits the work differently: partition the map into nested cells once, then, whenever traffic changes, recompute only the distances across each cell's boundary, which takes seconds. The open-source OSRM engine offers both: contraction hierarchies, and a multi-level Dijkstra in the customisable style. Commercial services rarely document their exact methods, so treat any claim about a particular product with care; the published research and the open-source engines show the shape of the solution.
Common misconceptions
Misconception
"Negative edges? Add a constant to every weight to make them positive." This changes which path is shortest, because a path with more edges gains more of the constant. With edges of weight 1 and of weights and , the two-edge path is shorter (0 against 1); add 2 to every edge and it becomes longer (4 against 3). Reweighting that does preserve shortest paths must use vertex potentials, as A*'s reduced weights do (Johnson's all-pairs algorithm computes such potentials with Bellman–Ford).
Misconception
"Dijkstra works with negative edges if you let it re-settle vertices." Then it is no longer Dijkstra: with negative edges such a "label-correcting" variant can take exponential time on some graphs. Use Bellman–Ford, or reweight first.
Misconception
"A is always faster than Dijkstra."* It is never worse in vertices settled when the heuristic is consistent, but a weak heuristic saves little and adds the cost of computing for every vertex. An inadmissible heuristic can be faster still, at the price of returning a path that is not shortest.
Misconception
"Longest paths are just shortest paths with negated weights." Negating turns every cycle of positive weight into a negative cycle, and the longest simple path problem is NP-hard in general (it contains the Hamiltonian path problem). In a DAG there are no cycles, and longest paths are easy: relax edges in topological order. Project managers do exactly this to find a schedule's critical path.
Exercises
1. Shortest paths
Warm-upHumanA directed graph has these edges and weights:
| Edge | Weight | Edge | Weight |
|---|---|---|---|
| S → A | 4 | B → C | 5 |
| S → B | 1 | C → T | 3 |
| B → A | 2 | B → D | 7 |
| A → C | 1 | D → T | 1 |
What is the shortest-path distance from S to T?
2. Shortest paths
Warm-upHumanA directed graph has 8 vertices, some negative edge weights, and no negative cycles. In the worst case, how many rounds of "relax every edge" does Bellman–Ford need before every distance from the source is guaranteed correct?
3. Shortest paths
CoreHumanA robot moves on a grid one square at a time, up, down, left or right (no diagonal moves), and each move costs 1. Some squares are blocked. The robot is at and the goal is at . Which of these heuristics are admissible for A*? Select all that apply.
4. Shortest paths
CoreHumanTo look for currency arbitrage, each exchange rate (one unit of currency buys units of ) becomes an edge from to . Which edge weight turns "a cycle of exchanges that multiplies your money by more than 1" into "a negative cycle"?
5. Shortest paths
CoreComputationalImplement the Floyd–Warshall algorithm. all_pairs(n, edges) receives vertices 0 to n - 1 and a list of directed edges (u, v, w); weights may be negative, and there may be several edges between the same pair (keep the lightest). Return an n × n list of lists D where D[i][j] is the shortest-path distance from i to j (math.inf if j is unreachable, and D[i][i] = 0). If the graph contains a negative cycle, raise ValueError.
6. Shortest paths
StretchComputationalA taxi company wants to know how many different fastest routes exist from its depot to each address, to spread drivers across them. Write count_shortest_paths(graph, s) for a directed graph graph (a dict mapping each vertex to a list of (neighbour, weight) pairs, with positive integer weights). Return a dict mapping every vertex reachable from s to the number of distinct shortest paths from s to it (with s itself mapped to 1).
Do it in one run of Dijkstra's algorithm, : do not enumerate paths.
7. Shortest paths
CoreHumanA routing engine uses contraction hierarchies. Which statement best describes what it computes in advance, and why that makes queries fast?
Further reading and resources
- A note on two problems in connexion with graphs · Edsger W. Dijkstra · 1959Three pages, two algorithms (shortest paths and minimum spanning trees).
- On a routing problem · Richard Bellman · 1958
- Algorithm 97: Shortest path · Robert W. Floyd · 1962
- A Formal Basis for the Heuristic Determination of Minimum Cost Paths · Peter E. Hart, Nils J. Nilsson and Bertram Raphael · 1968The A* paper, from the Shakey robot project at the Stanford Research Institute.
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks · Robert Geisberger, Peter Sanders, Dominik Schultes and Daniel Delling · 2008
- Customizable Route Planning · Daniel Delling, Andrew V. Goldberg, Thomas Pajor and Renato F. Werneck · 2011
- Route Planning in Transportation Networks · Hannah Bast and others · 2016The standard survey of the speed-up techniques used by modern routing engines.
- Open Source Routing Machine (OSRM)An open-source routing engine for OpenStreetMap data, offering both contraction hierarchies and multi-level Dijkstra.
- RFC 2328: OSPF Version 2 · J. Moy · 1998An internet routing protocol in which every router runs Dijkstra's algorithm.