Shortest paths

Breadth-first search finds routes with the fewest edges, but real networks have edges of different lengths: roads have distances and travel times, network links have latencies, and flights have prices. This lesson finds shortest paths in weighted graphs. Dijkstra's algorithm handles non-negative weights in \(O((n + m)\log n)\) time and is the workhorse behind route planners. Bellman–Ford handles negative weights and detects negative cycles, at a higher cost. For DAGs, a single pass in topological order solves the problem in linear time and also finds the longest paths used in project scheduling.

The single-source shortest-path problem

In a weighted directed graph, each edge \((u, v)\) has a weight \(w(u, v)\), and the weight of a path is the sum of its edge weights. The distance \(\delta(s, v)\) is the minimum weight of a path from \(s\) to \(v\), or infinity if \(v\) is unreachable. The single-source problem asks for \(\delta(s, v)\) for every vertex \(v\), together with the paths. An undirected road can be modeled as two directed edges, one each way. Shortest paths have optimal substructure: any part of a shortest path is itself a shortest path between its endpoints, because a shorter part could be swapped in to shorten the whole path.

Negative weights need care. They arise naturally, for example as rebates in a cost network or as logarithms of exchange rates. If a cycle reachable from \(s\) has negative total weight, going around it repeatedly makes paths arbitrarily cheap, so shortest paths are undefined for vertices reachable from that cycle. Algorithms must either forbid negative weights or detect negative cycles.

Relaxation

All the algorithms in this lesson maintain an estimate \(d[v]\) of the distance to each vertex, starting with \(d[s] = 0\) and \(d[v] = \infty\) for all others, and a parent pointer for each vertex. The single operation that improves estimates is relaxation of an edge \((u, v)\): if going through \(u\) gives a shorter route to \(v\), take it.

Relaxation never makes an estimate wrong in the dangerous direction: every \(d[v]\) is always the weight of some actual path, so \(d[v] \ge \delta(s, v)\) at all times. The algorithms differ only in which edges they relax and in what order. Relax the right edges in the right order and every estimate falls to the true distance.

Dijkstra's algorithm

Dijkstra's algorithm, published by Edsger Dijkstra in 1959, works for graphs with non-negative edge weights. It grows a set \(S\) of vertices whose distances are final. At each step it chooses the vertex \(u\) outside \(S\) with the smallest estimate \(d[u]\), adds it to \(S\), and relaxes every edge leaving \(u\). With all weights non-negative, the smallest estimate outside \(S\) is guaranteed to be exact, so the algorithm never needs to revisit a vertex. It is a greedy algorithm, a design technique lesson 11 studies in general.

Why is the chosen vertex's estimate exact? Suppose \(u\) is chosen but some shorter path \(P\) from \(s\) to \(u\) exists. \(P\) starts inside \(S\) and must leave \(S\) at some edge \((x, y)\), with \(x \in S\) and \(y\) outside. Since \(x\)'s distance is final and its edges were relaxed, \(d[y] \le \delta(s, x) + w(x, y)\), which is at most the weight of \(P\) because the rest of \(P\) after \(y\) has non-negative weight. So \(d[y] \le w(P) < d[u]\), contradicting the choice of \(u\) as the vertex with the smallest estimate. The argument fails exactly when the rest of \(P\) could have negative weight.

import heapq

def dijkstra(adj, s):
    dist = {s: 0}
    parent = {s: None}
    done = set()
    pq = [(0, s)]                        # (estimate, vertex)
    pops = 0
    while pq:
        du, u = heapq.heappop(pq); pops += 1
        if u in done:
            continue                     # stale entry: lazy deletion
        done.add(u)
        for v, w in adj[u]:
            nd = du + w
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, parent, pops

def route(parent, t):
    out = []
    while t is not None:
        out.append(t); t = parent[t]
    return out[::-1]

adj = {'s': [('a', 4), ('b', 1)], 'a': [('c', 1)], 'b': [('a', 2), ('d', 5)],
       'c': [('d', 1), ('t', 6)], 'd': [('t', 2)], 't': []}
dist, parent, pops = dijkstra(adj, 's')
print('distances:', dict(sorted(dist.items())))
print('route to t:', ' -> '.join(route(parent, 't')), 'weight', dist['t'])
print('heap pops:', pops)

distances: {'a': 3, 'b': 1, 'c': 4, 'd': 5, 's': 0, 't': 7}
route to t: s -> b -> a -> c -> d -> t weight 7
heap pops: 9

The route to \(t\) is s, b, a, c, d, t with weight 7, longer in edges than the direct-looking s, b, d, t but lighter, which BFS would get wrong. The code uses a common trick: rather than decreasing a key inside the heap, which heapq does not support, it pushes a new entry and skips stale ones when popped. Each edge causes at most one push, so the heap holds at most \(m\) entries and each operation costs \(O(\log m) = O(\log n)\).

Negative weights and Bellman–Ford

With a negative edge, Dijkstra can finalize a vertex too early. In the graph with edges \(s \to a\) of weight 2, \(s \to b\) of weight 5 and \(b \to a\) of weight \(-4\), Dijkstra finalizes \(a\) at distance 2, but the path through \(b\) costs 1. The Bellman–Ford algorithm avoids any greedy choice. It relaxes every edge, in any order, \(n - 1\) times. After round \(i\), every vertex whose shortest path uses at most \(i\) edges has its correct distance, by induction on \(i\). Since a shortest path without cycles has at most \(n - 1\) edges, \(n - 1\) rounds suffice, for a total of \(\Theta(nm)\) time.

Bellman–Ford also detects negative cycles. After \(n - 1\) rounds, run one more pass over the edges. If any edge can still be relaxed, some estimate is still falling, which can only happen if a negative cycle is reachable from \(s\). This makes Bellman–Ford the standard tool for detecting arbitrage in currency markets: with edge weights \(-\log(\text{rate})\), a cycle of trades that multiplies money corresponds to a cycle of negative total weight. Distance-vector routing protocols, such as RIP on older networks, are distributed versions of Bellman–Ford.

import heapq, math

def bellman_ford(vertices, edges, s):
    d = {v: math.inf for v in vertices}
    d[s] = 0
    for _ in range(len(vertices) - 1):
        changed = False
        for u, v, w in edges:
            if d[u] + w < d[v]:
                d[v] = d[u] + w; changed = True
        if not changed:
            break                         # early exit: estimates are final
    cycle = any(d[u] + w < d[v] for u, v, w in edges)
    return d, cycle

def dijkstra_dist(vertices, edges, s):
    adj = {v: [] for v in vertices}
    for u, v, w in edges:
        adj[u].append((v, w))
    d, done, pq = {s: 0}, set(), [(0, s)]
    while pq:
        du, u = heapq.heappop(pq)
        if u in done: continue
        done.add(u)
        for v, w in adj[u]:
            if v not in done and du + w < d.get(v, math.inf):
                d[v] = du + w; heapq.heappush(pq, (d[v], v))
    return d

V = ['s', 'a', 'b']
E = [('s', 'a', 2), ('s', 'b', 5), ('b', 'a', -4)]
print('Dijkstra    :', dijkstra_dist(V, E, 's'))
print('Bellman-Ford:', bellman_ford(V, E, 's'))

rates = {('CAD', 'USD'): 0.73, ('USD', 'EUR'): 0.92, ('EUR', 'CAD'): 1.50}   # illustrative rates
cur = ['CAD', 'USD', 'EUR']
E2 = [(a, b, -math.log(r)) for (a, b), r in rates.items()]
print('product of rates around the cycle:', round(0.73 * 0.92 * 1.50, 4))
print('negative cycle (arbitrage)?', bellman_ford(cur, E2, 'CAD')[1])

Dijkstra    : {'s': 0, 'a': 2, 'b': 5}
Bellman-Ford: ({'s': 0, 'a': 1, 'b': 5}, False)
product of rates around the cycle: 1.0074
negative cycle (arbitrage)? True

Dijkstra reports a distance of 2 to \(a\), which is wrong; Bellman–Ford finds 1. The illustrative exchange rates multiply to a little more than 1 around the cycle, so converting money around it would make a small profit, and Bellman–Ford reports the corresponding negative cycle. Real markets close such gaps within milliseconds, and transaction fees usually erase them.

Shortest and longest paths in a DAG

If the graph is a DAG, there is an even simpler method. Topologically sort the vertices, as in lesson 8, and relax the edges leaving each vertex in that order. When a vertex is processed, every edge into it has already been relaxed, so its estimate is final. This takes \(\Theta(n + m)\) time and works with negative weights, since a DAG has no cycles at all.

Negating every weight turns the same method into a longest-path algorithm, which is otherwise a hard problem in general graphs. In project scheduling, tasks are vertices or edges of a DAG weighted by their durations, and the longest path from start to finish is the critical path: the minimum time to complete the project, and the chain of tasks where any delay delays everything. The critical path method used in construction planning, as in CON-210, is exactly this computation.

def dag_longest(order, adj, dur):
    """Earliest finish times; tasks given in topological order."""
    start = {t: 0 for t in order}
    via = {t: None for t in order}
    for u in order:
        for v in adj[u]:
            if start[u] + dur[u] > start[v]:     # relax for the longest path
                start[v] = start[u] + dur[u]
                via[v] = u
    finish = {t: start[t] + dur[t] for t in order}
    end = max(finish, key=finish.get)
    path, t = [], end
    while t is not None:
        path.append(t); t = via[t]
    return finish[end], path[::-1]

dur = {'design': 5, 'permits': 10, 'foundation': 7, 'framing': 12, 'electrical': 6, 'plumbing': 5, 'finish': 8}
adj = {'design': ['permits', 'foundation'], 'permits': ['framing'], 'foundation': ['framing'],
       'framing': ['electrical', 'plumbing'], 'electrical': ['finish'], 'plumbing': ['finish'], 'finish': []}
order = ['design', 'permits', 'foundation', 'framing', 'electrical', 'plumbing', 'finish']
length, path = dag_longest(order, adj, dur)
print('project length:', length, 'days')
print('critical path :', ' -> '.join(path))

project length: 41 days
critical path : design -> permits -> framing -> electrical -> finish

For distances between every pair of vertices, running Dijkstra from each vertex costs \(O(n(n + m)\log n)\) on non-negative graphs, while the Floyd–Warshall algorithm, a dynamic-programming method covered in CMPUT-304, handles any weights in \(\Theta(n^3)\). Route planners for continental road networks go further, precomputing shortcuts so a query touches only a few thousand vertices out of millions; robot path planners in ROB-340 use A*, a Dijkstra variant guided by a distance estimate to the goal.