Shortest Paths: Choosing an Algorithm by Weights and Pairs

A shortest path in a weighted graph is the route between two vertices whose edge weights add up to the least, and four algorithms find one, each suited to a different graph. This card defines the terms the four share and gives the decision that picks among them; the cards after it take one algorithm each, on the same graph.

In a weighted graph each edge carries a number, its weight, such as a distance, a fare or a time. The length of a path is the sum of its weights, so the shortest path need not be the one with the fewest edges. In the graph below, A->C->E has two edges and costs 13, while A->B->C->D->E has four and costs 8.

Every algorithm in the topic keeps a distance for each vertex, the length of the best path to it found yet, starting at 0 for the source and ∞ for the rest. Each improves those distances in one way, called relaxing an edge: for an edge u->v of weight w, if the distance to u plus w is less than the distance to v, lower v's distance to that sum and note u as v's parent, the vertex before it on the path. Following parents back from a vertex rebuilds its path.

A weight may be negative, such as a rebate or a gain. A negative cycle is a cycle whose weights add up to less than 0: going round it again lowers the length every time, so a vertex reachable through it has no shortest path at all.

Three questions about the graph decide which algorithm to use.