The single-source shortest path problem finds the minimum-weight path from one starting vertex to every other vertex in a weighted graph. Dijkstra’s algorithm solves it greedily by repeatedly exploring the closest known vertex, updating distances and predecessor edges when shorter routes appear. section 4.4
Dijkstra’s algorithm proceeds as follows:
- Add the starting vertex to an ascending priority queue. section 4.4
- Remove the closest vertex, inspect every neighbor, and record a new distance and predecessor edge when the route is shorter. section 4.4
- Repeat until the queue is empty, then return distances and predecessor information for reconstructing paths. section 4.4
A route from Los Angeles to Boston
The computed route passes through Riverside, Chicago, and Detroit: Los Angeles → Riverside → Chicago → Detroit → Boston. Its total weight is 2605, while the distance from Los Angeles to Los Angeles is 0.
