Skip to content
LumenaryAcademy
Algorithms 75 min

Shortest paths

From here to there at the least cost — Dijkstra, Bellman–Ford, Floyd–Warshall and A*, and how map services answer in milliseconds.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

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:

AlgorithmProblemWeightsTime
Dijkstraone source to allnon-negativeO((V+E)log⁡V)O((V + E)\log V) with a binary heap
Bellman–Fordone source to allany; detects negative cyclesO(VE)O(VE)
Floyd–Warshallall pairsany; detects negative cyclesO(V3)O(V^3)
A*one source to one targetnon-negative, plus a heuristicoften 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.

DefinitionsH

Definitions

Definition— path weight and distance

In a directed graph with edge weights w(u,v)w(u, v), the weight of a path is the sum of its edge weights. The distance δ(s,v)\delta(s, v) is the least weight of any path from ss to vv; it is ∞\infty 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 ss and can reach vv, then going round it again and again makes paths to vv arbitrarily light, and δ(s,v)\delta(s, v) is undefined (or −∞-\infty).

Definition— relaxation

Shortest-path algorithms keep an estimate d[v]d[v] for each vertex, initially d[s]=0d[s] = 0 and d[v]=∞d[v] = \infty otherwise. Relaxing an edge (u,v)(u, v) means: if d[u]+w(u,v)<d[v]d[u] + w(u, v) < d[v], set d[v]=d[u]+w(u,v)d[v] = d[u] + w(u, v) and parent[v]=u\text{parent}[v] = u.

ExplanationH

The common core: relaxation

Three simple facts underlie every algorithm in this lesson.

  1. Subpaths of shortest paths are shortest paths. If the best route from ss to vv passes through uu, its first part is a best route from ss to uu; otherwise we could swap in a better first part and improve the whole. This is the optimal substructure of dynamic programming.
  2. Triangle inequality. For every edge (u,v)(u, v): δ(s,v)≤δ(s,u)+w(u,v)\delta(s, v) \le \delta(s, u) + w(u, v), since one way to reach vv is to reach uu optimally and then take the edge.
  3. Estimates never undershoot. Throughout any sequence of relaxations, d[v]≥δ(s,v)d[v] \ge \delta(s, v), because d[v]d[v] is always either ∞\infty or the weight of an actual path (the one traced by the parent pointers). And once d[v]=δ(s,v)d[v] = \delta(s, v), it never changes again.

So an algorithm is correct if it relaxes the right edges in a good enough order that every d[v]d[v] comes down to δ(s,v)\delta(s, v). 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.

ExplanationH

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.

text
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 uu is settled, d[u]=δ(s,u)d[u] = \delta(s, u). Consequently Dijkstra's algorithm computes all distances from ss, and the parent pointers form a tree of shortest paths. With a binary heap and lazy deletion it runs in O((V+E)log⁡V)O((V + E) \log V) time.

Proof

Suppose not, and let uu be the first vertex settled with d[u]>δ(s,u)d[u] > \delta(s, u) (so u≠su \ne s, and uu is reachable). Take a shortest path from ss to uu, and let yy be the first vertex on it that is not yet settled at the moment uu is popped; let xx be the vertex before yy on the path. Then xx is settled, and since it was settled before uu, d[x]=δ(s,x)d[x] = \delta(s, x); when xx was settled, the edge (x,y)(x, y) was relaxed, so

d[y]≤δ(s,x)+w(x,y)=δ(s,y)≤δ(s,u)<d[u].d[y] \le \delta(s, x) + w(x, y) = \delta(s, y) \le \delta(s, u) < d[u].

The equality uses fact 1 (the path up to yy is shortest); the next inequality uses non-negative weights (the rest of the path from yy to uu cannot have negative weight). So yy sits in the heap with a smaller key than uu, and the heap would have popped yy before uu. 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 E+1E + 1 entries, and every push and pop costs O(log⁡E)=O(log⁡V)O(\log E) = O(\log V) (since E≤V2E \le V^2).

∎

Why negative edges break it. The proof's key step is that extending a path never makes it lighter. Take edges s→as \to a of weight 2, s→bs \to b of weight 3, b→ab \to a of weight −2-2 and a→ca \to c of weight 1. Dijkstra settles aa at distance 2 and, through it, gives cc distance 3; only then does it settle bb and find the lighter route to aa, of weight 3−2=13 - 2 = 1. But aa is already settled, so its edges are never relaxed again, and cc keeps the wrong distance 3 instead of 2. The error spreads to everything reached from aa.

python
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")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

With a Fibonacci heap the bound improves to O(E+Vlog⁡V)O(E + V \log V) (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.

ExplanationH

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, V−1V - 1 times.

Theorem— Bellman–Ford

After ii rounds of relaxing all edges, d[v]d[v] is at most the weight of the lightest path from ss to vv that uses at most ii edges. If no negative cycle is reachable from ss, then after V−1V - 1 rounds d[v]=δ(s,v)d[v] = \delta(s, v) for every vv. A negative cycle is reachable from ss if and only if some edge can still be relaxed in a further, VV-th round. The running time is O(VE)O(VE).

Proof

The first claim is by induction on ii: a lightest path with at most ii edges ending in the edge (u,v)(u, v) consists of a path to uu with at most i−1i - 1 edges (whose weight is ≥d[u]\ge d[u] after round i−1i - 1 by induction) plus (u,v)(u, v), and round ii relaxes (u,v)(u, v). 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 V−1V - 1 edges, and after V−1V - 1 rounds d[v]≤δ(s,v)d[v] \le \delta(s, v); with fact 3, equality.

If no negative cycle is reachable, all dd values are final after V−1V - 1 rounds, so nothing can be relaxed in round VV. Conversely, suppose a reachable cycle v1→⋯→vk→v1v_1 \to \cdots \to v_k \to v_1 has negative weight but no edge can be relaxed, so d[vj+1]≤d[vj]+w(vj,vj+1)d[v_{j+1}] \le d[v_j] + w(v_j, v_{j+1}) around the cycle. Adding these kk inequalities, the dd terms cancel, leaving 0≤0 \le 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 rabr_{ab} units of currency bb, a cycle of exchanges multiplies your money by the product of its rates. Give the edge from aa to bb the weight −log⁡rab-\log r_{ab}. Then a product greater than 1 corresponds to a sum of logarithms greater than 0, which is a negative cycle. Bellman–Ford finds it.

python
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")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

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 O(V(V+E)log⁡V)O(V (V + E) \log V), 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 1,…,V1, \ldots, V, and let Dk[i][j]D_k[i][j] be the weight of the lightest path from ii to jj whose intermediate vertices all lie in {1,…,k}\{1, \ldots, k\}. A best such path either avoids vertex kk, or passes through it exactly once (assuming no negative cycles), splitting into a path i⇝ki \leadsto k and a path k⇝jk \leadsto j that use only intermediates below kk:

Dk[i][j]=min⁡(Dk−1[i][j], Dk−1[i][k]+Dk−1[k][j]),D_k[i][j] = \min\big(D_{k-1}[i][j],\ D_{k-1}[i][k] + D_{k-1}[k][j]\big),

starting from D0D_0 = the edge weights (0 on the diagonal, ∞\infty where there is no edge). That is three nested loops, kk outermost, over a single V×VV \times V matrix updated in place: O(V3)O(V^3) time and O(V2)O(V^2) 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.

ExplanationH

A*: searching towards the goal

Dijkstra from ss 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 tt, 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 h(v)h(v), an estimate of the remaining distance from vv to tt, and orders the priority queue by f(v)=d[v]+h(v)f(v) = d[v] + h(v): distance so far plus estimated distance to go. Vertices in the direction of the target get priority.

  • hh is admissible if it never overestimates: h(v)≤δ(v,t)h(v) \le \delta(v, t) for every vv. Then A* returns a shortest path.
  • hh is consistent if h(u)≤w(u,v)+h(v)h(u) \le w(u, v) + h(v) for every edge, and h(t)=0h(t) = 0. Consistency implies admissibility, and then, like Dijkstra, A* never needs to settle a vertex twice.

The cleanest proof uses reduced weights w′(u,v)=w(u,v)−h(u)+h(v)w'(u, v) = w(u, v) - h(u) + h(v). Consistency says exactly that w′≥0w' \ge 0. Along any path from ss to tt the hh terms telescope, so every path's reduced weight equals its real weight minus h(s)h(s) (since h(t)=0h(t) = 0): the same paths are shortest under both weightings. And A* on ww makes exactly the choices that Dijkstra makes on w′w', which is correct because w′w' 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 ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2| is admissible. With h=0h = 0, A* is Dijkstra; the closer hh 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 hh up (weighted A*) explores even less but may return a slightly longer path.

python
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}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Both find a path of the same length; A* settles far fewer cells, even though the wall forces it to look around.

ExplanationH

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.

  1. 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.)
  2. Contract the vertices one at a time in that order. Contracting vv removes it from the graph; for every pair of its remaining neighbours uu and ww, a small local search looks for a witness, another path from uu to ww that is no longer than u→v→wu \to v \to w. If there is none, add a shortcut edge u→wu \to w with the weight of u→v→wu \to v \to w. Distances among the remaining vertices are preserved.
  3. Query with a bidirectional Dijkstra, forwards from ss and backwards from tt, 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 misconceptionsH

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 s→ts \to t of weight 1 and s→a→ts \to a \to t of weights −1-1 and 11, 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 hh 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

Exercises

1. Shortest paths

Warm-upHuman

A 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-upHuman

A 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

CoreHuman

A 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 (x,y)(x, y) and the goal is at (gx,gy)(g_x, g_y). Which of these heuristics are admissible for A*? Select all that apply.

Choose all that apply

4. Shortest paths

CoreHuman

To look for currency arbitrage, each exchange rate rr (one unit of currency aa buys rr units of bb) becomes an edge from aa to bb. Which edge weight turns "a cycle of exchanges that multiplies your money by more than 1" into "a negative cycle"?

Choose one

5. Shortest paths

CoreComputational

Implement 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.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Shortest paths

StretchComputational

A 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, O((V+E)log⁡V)O((V + E) \log V): do not enumerate paths.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Shortest paths

CoreHuman

A routing engine uses contraction hierarchies. Which statement best describes what it computes in advance, and why that makes queries fast?

Choose one

Further reading and resources