Shortest Paths

Least-weight paths and Dijkstra's relaxation.

The idea

A shortest path between two vertices of a weighted graph — one whose every edge carries a number, its weight, such as a distance, a travel time, or a toll — is a path of least possible total weight. The length of a path here is the sum of the weights of its edges, not the count of them, and the two measures differ: a two-edge detour along cheap edges can beat a single expensive edge.

Algorithm.

Algorithm: Dijkstra Input: a weighted graph with no negative weights, a source vertex s Output: the shortest distance from s to every vertex 1. dist(s) = 0; dist(v) = ∞ for every other vertex v // dist(v) = v's tentative distance, the best route found so far 2. u = an unsettled vertex of smallest dist; mark u settled // a settled dist is the true shortest distance 3. relax each edge uw leaving u: if dist(u) + weight(uw) < dist(w), set dist(w) = dist(u) + weight(uw) 4. if a reachable vertex is still unsettled, go to step 2 5. return the settled distances

A settled value is final. Any other route to the vertex being settled passes through some still-unsettled vertex, whose tentative distance is already at least as large, and with no negative weights the route only lengthens from there.

Ways to work on it

• Walkthrough. Shortest distances in a weighted graph.
• Practice. Find a shortest distance.
• Hardest. Trace one Dijkstra relaxation and compare it with a naive greedy walk.

Not sure where to start? Take the ten-question placement test.