The problem

Breadth-first search (GRPH-2) finds the route with the fewest edges. On a real railway, lines take different times, and the route with the fewest changes is not always the quickest. This station is about routes where each edge has a length.

Edges with lengths

Give every edge a number, its weight: minutes of travel, kilometres, a fare. A graph with weights is a weighted graph. The length (or weight, or cost) of a route is the sum of the weights of its edges. A shortest route from s to t is a route whose length is as small as possible, and that smallest length is the distance from s to t, written δ(s, t) (the Greek letter delta). If t cannot be reached, the distance is ∞ (infinity).

When every weight is 1, the length of a route is its number of edges, and breadth-first search already solves the problem. With other weights it does not. Step through the first variant of the figure: the route with the fewest edges takes 10 minutes, and a route with one more edge takes 9.

In code, store the weight with each neighbour. An adjacency list of pairs is the usual choice, and the edge list of triples (u, v, w) from GRPH-1 is the other:

def build(n, edges, directed=False):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        if not directed:
            adj[v].append((u, w))
    return adj

This station asks three kinds of question. One start to one target: the quickest way from here to there. One start to every vertex (single-source shortest paths): most methods answer this anyway, because they cannot be sure about the target until they know about everything nearer. Every pair (all-pairs shortest paths): a table of distances between all stations.

Distances and relaxing

Every method in this station keeps two lists. dist[v] is the length of the best route to v found so far (∞ at first, 0 for the start). parent[v] is the vertex just before v on that route. Both are changed by one small step, called relaxing an edge:

import math

dist = [math.inf] * n
dist[s] = 0

def relax(u, v, w):
    if dist[u] + w < dist[v]:     # a better route to v, through u
        dist[v] = dist[u] + w
        parent[v] = u

math.inf is Python’s infinity: it is larger than every number, and math.inf + 5 is still math.inf, so relaxing an edge from a vertex not yet reached changes nothing. The second variant of the figure relaxes edges one at a time, by hand. A time can go down more than once, and the parent changes when it does.

Two facts about relaxing hold whatever the order. First, dist[v] is never smaller than the true distance: each value is the length of a real route, made one edge at a time. Second, it only goes down. So a method is correct if it relaxes the right edges in the right order until every value equals the distance. The methods of this station differ only in that order:

• 0-1 BFS (lesson 2) and Dijkstra (lesson 3) relax the edges out of the nearest vertex next;
• Bellman–Ford (lesson 4) relaxes every edge, again and again;
• a DAG (lesson 6) relaxes edges in topological order, each once;
• A* (lesson 7) relaxes the edges out of the vertex that seems nearest to the target.

Two facts about shortest routes

Parts of shortest routes are shortest routes. If s → … → u → … → t is a shortest route from s to t, then its part from s to u is a shortest route from s to u. If it were not, a shorter route to u could replace that part, and the whole route would get shorter. This is the “optimal substructure” of DYNP-1, and it is why one parent per vertex is enough: the shortest routes from s to every vertex fit together into one tree, the shortest-path tree (the shaded edges in the figure).

The triangle rule. For every edge u → v with weight w, the distances satisfy

Going to u by a shortest route and then along the edge is one way to reach v, so the best way to v is at most that long. An edge where the two sides are equal is called tight: it lies on some shortest route. When no edge can be relaxed any more, the triangle rule holds for every edge, and that is how every method knows it has finished.

These two facts also give a way to check claimed distances d without running a search again. The claims are right when d[s] = 0, no edge breaks the triangle rule, and every vertex with a number is reached from s along tight edges. The last part matters: with edges of weight 0, tight edges can go round a loop that never starts from s, and numbers that are too small can still pass the first two checks. That is PATH-P1.

Negative edges and negative cycles

Weights can be negative: a refund on a ticket, energy gained going downhill, a profit. A negative edge is no problem in itself. But a negative cycle, a cycle whose weights add up to less than 0, is: going round it once more always makes a route cheaper, so vertices reachable through it have no shortest route at all. Their distance is said to be −∞. A shortest route never needs to repeat a vertex when there is no negative cycle (cutting out a loop of length 0 or more never makes a route longer), so a shortest route then has at most V − 1 edges. Lesson 4 uses this.

In an undirected graph, a negative edge is itself a negative cycle: go along it and straight back. So negative weights only make sense on directed edges.

Which method when

Here log V is “how many times you can halve V”, and V³ means V · V · V. Now try PATH-P1, Are these the shortest times?