
Dijkstra's algorithm finds the shortest path from one starting node to every reachable node in a weighted graph whose edge weights are nonnegative. It keeps a tentative distance for each node, repeatedly visits the unvisited node with the smallest tentative distance, and relaxes that node's edges. In the worked example below, the shortest route from A to F is A–C–D–E–F with total weight 8.
The important idea is that the algorithm does not chase the route with the fewest edges. It compares accumulated cost. That distinction is why a tempting three-edge route can lose to a cheaper four-edge route. This trace is for anyone learning shortest paths or trying to understand what a distance table and predecessor array actually record.
For every node, store three pieces of information: its current tentative distance from the start, whether it has been visited, and its predecessor on the best route found so far. Set the start node's distance to 0 and every other distance to infinity. No route to those nodes is known yet.
At each step, select the unvisited node with the smallest tentative distance. Then relax each edge leaving it: candidate distance = current node's distance + edge weight. If the candidate is smaller than the neighbor's recorded distance, replace the distance and set the current node as that neighbor's predecessor. Once a node is visited, its distance is final under Dijkstra's nonnegative-weight condition.
Use an undirected graph with nodes A through F. Its weighted edges are A–B 4, A–C 2, B–D 5, C–D 3, C–E 7, D–E 1, D–F 6, and E–F 2. We want the shortest path from A to F. All weights are nonnegative, so Dijkstra's algorithm applies.
Initialize the table with A = 0 and B, C, D, E, F = infinity. The predecessor of every node is blank. The visited set is empty.
A has the smallest tentative distance, 0. Relax A–B: 0 + 4 = 4, so B becomes 4 with predecessor A. Relax A–C: 0 + 2 = 2, so C becomes 2 with predecessor A. Mark A visited. The next node is C because 2 is smaller than B's 4.
From C, the route back to A would cost 2 + 2 = 4, which cannot improve A's 0. For D, 2 + 3 = 5, so record D = 5 and predecessor C. For E, 2 + 7 = 9, so record E = 9 and predecessor C. Mark C visited.
B is now the smallest unvisited node at 4. Its route to D would cost 4 + 5 = 9. D already has the better tentative distance 5, so nothing changes. This is an important part of relaxation: a candidate route is considered, but it only replaces the record when it is strictly cheaper. Mark B visited.
D has distance 5. Reaching E through D costs 5 + 1 = 6, which improves E from 9 to 6; change E's predecessor from C to D. Reaching F costs 5 + 6 = 11, so set F = 11 and predecessor D. Mark D visited.
E is next at 6. The candidate route to F costs 6 + 2 = 8, improving F from 11 to 8 and changing its predecessor to E. Mark E visited. F is now the smallest unvisited node at 8. Once F is visited, the shortest distance from A to F is final, so a destination-only search can stop.

The route A–C–E–F uses three edges, but its weight is 2 + 7 + 2 = 11. The winning route A–C–D–E–F uses four edges and weighs 2 + 3 + 1 + 2 = 8. Dijkstra's algorithm minimizes total weight, not hop count. Breadth-first search can minimize the number of edges in an unweighted graph; it does not solve this weighted version unless every edge has the same cost.
The final distance tells us the cost, but the predecessor links tell us the route. Start at F and follow the chain backward: predecessor(F) = E, predecessor(E) = D, predecessor(D) = C, and predecessor(C) = A. This gives F–E–D–C–A. Reverse it to obtain A–C–D–E–F.
Notice that E's predecessor changed during the run. Its first known route came directly from C with cost 9. Visiting D revealed a better route with cost 6, so the algorithm updated both the distance and the predecessor. Keeping one without the other would leave the final route inconsistent.

A common mistake is choosing the smallest outgoing edge instead of the unvisited node with the smallest total tentative distance. Another is marking a node visited when it is first discovered. Discovery gives a provisional route; selection as the minimum unvisited node makes that route final. Also remember to update the predecessor whenever a relaxation improves a distance.
Standard Dijkstra's algorithm is not valid when reachable negative-weight edges exist. A later negative edge can undercut a distance that the algorithm already treated as final. Use an algorithm designed for negative weights, such as Bellman–Ford, when that condition matters. Negative cycles require still different handling because no finite shortest path exists through a repeatedly usable negative cycle.
After visiting C, B has tentative distance 4 and D has 5. Dijkstra's rule chooses the smallest total tentative distance, so B must be processed first even though its relaxation produces no improvement.
E improves from 9 to 6 and its predecessor changes from C to D. F is discovered with distance 11 and predecessor D.
No. A tentative distance is not final when first assigned. Visiting E later improves F to 8. You may stop when F becomes the minimum unvisited node and is visited.
Edsger W. Dijkstra, A Note on Two Problems in Connexion with Graphs (1959)
Massachusetts Institute of Technology OpenCourseWare: Lecture 13, Shortest Paths II—Dijkstra
Cornell University CS 2112: Shortest Paths
Princeton University Algorithms, 4th Edition: DijkstraSP implementation
Appunti, quiz, podcast, flashcard e chat — da un solo upload.
Prova il primo appunto gratis