In a weighted graph, distance is the accumulated edge weight from a starting vertex. Dijkstra’s algorithm tracks the shortest distance found so far to each vertex, updating it when a cheaper route appears. A nil value means the distance is not yet known. section 4.4
Dijkstra’s algorithm uses distances to guide its search:
- Start the root at the supplied start distance, typically zero, and place it in a priority queue. section 4.4
- Explore the closest queued vertex; for each neighbor, record the new distance and connecting edge if no route is known or the new route is shorter. section 4.4
- Continue until the queue is empty, then return distances and the edges used to reach vertices. section 4.4
Routes from Los Angeles
In a weighted city graph, the distance to Boston is 2605 via Riverside, Chicago, and Detroit. The distance records total route weight, while the stored edges reconstruct the path.
