Finding the fastest route from A to B
The problem is to find the shortest path from one point to another on a map. Navigation apps do this constantly: a map is translated into a mathematical object, and an algorithm searches that object for a route with minimum total length.
The mathematical object is a directed graph. It consists of a set of nodes, usually written V, and a set of arcs, usually written A. An arc is an ordered pair such as (a,b), meaning travel is allowed from a to b. The reverse arc (b,a) is different and may or may not exist.
Every arc has a nonnegative length. We write the length of arc (i,j) as ℓ(i,j). The length of a path is the sum of the lengths of its arcs.
Chapter example graph
The lab below is preloaded with this graph.
In this graph, one shortest path from a to f is a → b → d → e → f, with total length 4+2+6+1=13.
Making the input and output precise
A path from a source node s to a target node t is a sequence of arcs. The first arc starts at s, each later arc starts where the previous arc ended, and the last arc ends at t.
Shortest path problem
Input. A directed graph G=(V,A), a source node s∈V, a target node t∈V, and a nonnegative length ℓ(i,j) for each arc (i,j)∈A.
Output. A path P from s to t.
Goal. Minimize the path length ∑(i,j)∈P ℓ(i,j).
Dijkstra’s algorithm actually computes more than one path: it finds the shortest path length from s to every reachable node. The path to a particular target can then be reconstructed by following the recorded predecessor values backward from the target to the source.
Interactive lab: build a graph and run Dijkstra’s algorithm
Use the tools to create a directed graph. Arc lengths must be nonnegative; this is the condition under which Dijkstra’s algorithm is valid. The example graph from the chapter is loaded by default.
Current best and from table
Step log and target path
Summary of Dijkstra’s algorithm
For every node i, the algorithm keeps a tentative value best(i): the length of the shortest path from s to i found so far. It also stores from(i), the node immediately before i on that current best path.
Dijkstra’s algorithm
0. Initialization
Set S = ∅. Set best(s)=0 and best(i)=∞ for all other nodes. Set from(i) to undefined.
1. One more shortest path found
Choose a node i∉S with the smallest tentative value best(i). Its shortest path length is now final.
2. Try extending this path by one arc
For each outgoing arc (i,j), compare best(i)+ℓ(i,j) to the current best(j). If it is smaller, set best(j)=best(i)+ℓ(i,j) and from(j)=i.
3. Repeat
Add i to S. If more nodes remain, go back to step 1.
The reason the smallest tentative value is safe to make final is the nonnegativity of the arc lengths. Once a tentative path is already the smallest among all frontier paths, adding more nonnegative arcs cannot produce a shorter way to reach that same node later.
Output: the shortest path tree
The output can be summarized by the arcs (from(i),i) for all nodes i≠s that are reachable from s. These arcs form a shortest path tree rooted at s. The unique path from s to i in this tree is a shortest path in the original graph.
In the lab, green arcs show the current predecessor tree. When the run is complete, the tree describes shortest paths from the source to all reachable nodes. The purple arcs show the current path from the source to the selected target.
Reconstructing a path
Start at the target. If from(f)=e, then the last arc is (e,f). Then look at from(e), and continue backward until the source is reached. Reverse the arcs to write the path from source to target.
Verifying a shortest path solution
After Dijkstra’s algorithm finishes, the distance values can be used to check the solution. For each arc (i,j), calculate the modified length
ℓ̄(i,j) = ℓ(i,j) + best(i) − best(j).
If the computed values are correct, every modified length is nonnegative. Arcs in the shortest path tree have modified length 0.
So a practical certificate is: check ℓ̄(i,j)≥0 for every arc, and check ℓ̄(i,j)=0 on the path or tree arcs. If both pass, the displayed shortest path is certified.
Verification table for the current graph
Modeling with shortest paths: line breaks
The chapter’s final modeling example converts paragraph formatting into a shortest path problem. Create a node for each word position. An arc from position i to a later position j means: put words i+1 through j on one line. The arc cost is the aesthetic cost of that line. A shortest path chooses the best sequence of line endings.
