Trace a shortest path one decision at a time

In a weighted graph, the shortest path minimizes the sum of edge weights. It need not use the fewest edges or look shortest on the screen. Weights might represent a toy travel cost or delay. Dijkstra's algorithm keeps the best distance found so far for each vertex, repeatedly selecting the unvisited vertex with the smallest tentative distance.

The algorithm requires nonnegative edge weights. Its useful invariant is that a selected vertex can be finalized: a route through a more distant unvisited vertex cannot later become cheaper by adding nonnegative weights. The picture illustrates this invariant; geometric distances and drawn edge lengths are not substitutes for reading the actual weights.

Consider an undirected graph with edges A–B of weight 4, A–C of weight 1, C–B of weight 2, B–D of weight 1 and C–D of weight 5. Start at A and seek D. This is a worked paper example; the module generates its own graphs rather than offering an editor for these five edges.

1. Initialize A at distance 0 and every other vertex at infinity. After exploring A, the tentative distances are B = 4 and C = 1.
2. Select C next because its distance is smaller. The route A–C–B costs 1 + 2 = 3, improving B from 4 to 3. The route A–C–D gives D a tentative distance of 6.
3. Select B at distance 3. Extending its route to D costs 3 + 1 = 4, improving D from 6 to 4.
4. Select D at distance 4. Follow its predecessor chain backwards: D came from B, B from C and C from A. The resulting route is A–C–B–D.

The winning route has three edges, while both alternatives listed have two. Breadth-first search minimizes the number of edges in an unweighted graph; it would not solve this weighted problem by simply treating every edge as equally costly.

1. Open Dijkstra's Algorithm and note the generated graph's source, target and edge weights.
2. Use Step to advance one decision at a time. Before each step, predict which unvisited vertex has the lowest tentative distance.
3. Whenever an edge is considered, add its weight to the current distance. A neighbor's distance changes only when the proposed sum is better than its previous value. This comparison is called relaxation.
4. After a route is found, add the displayed weights along the highlighted path. Compare the sum with the reported total, then reset and try another generated graph.

Several vertices can have equal tentative distances. A tie can change the order of exploration or which equal-cost predecessor is recorded without changing the minimum path cost. Do not infer an incorrect result just because two valid traces select different vertices in a tie.

For a directed paper example, let A→B cost 2, A→C cost 5 and C→B cost −10. Finalizing B at cost 2 would miss the cheaper route through C, whose total is −5. The nonnegative-weight argument no longer applies. Riano's generated demonstration uses positive weights, so this failure case should be reasoned about separately rather than entered as an unsupported control value.

An unreachable target has no finite shortest-path distance. A negative cycle reachable on a route to the target can remove the existence of a minimum altogether. Those are different cases from a costly but valid route. Other algorithms, such as Bellman–Ford, address different weight assumptions; their guarantees still depend on handling negative cycles.

Change the paper example's C–D edge from weight 5 to weight 1. The route A–C–D now costs 2, improving on the previous total of 4. Trace the tentative distances again and identify exactly which relaxation changes D's predecessor. Then explain why changing the visual positions of vertices alone should not alter a shortest path when the weights stay fixed.

Read the companion theory article and MIT OpenCourseWare: Dijkstra's algorithm for the nonnegative-weight argument and implementation choices.