Why does Dijkstra's algorithm not finalize the destination label 7 at university immediately when it first appears?

Conditions

• The graph is being processed by Dijkstra's algorithm.
• Vertices with circled labels are treated as already selected/settled.
• Uncircled labels are still tentative candidates.
• There exists at least one uncircled vertex with a label smaller than the target's current label.

Reasoning, step by step

1. Identify the current candidate label at the destination (university = 7).
2. Scan all uncircled vertices for their tentative labels.
3. Find the smallest uncircled label ($E = 4$).
4. Compare the smallest uncircled label with the destination label ($4 < 7$).
5. Conclude that the destination label cannot be finalized yet because a smaller candidate remains unsettled.
6. Process the smaller vertex (E) to see if it improves the destination label.

Example

In the video, the presenter explicitly states, "Now, we don't just conclude that seven must be the shortest distance because we've still got some other vertices to consider. So the smallest uncircled vertex is this other four down here." The vertex E with label 4 is circled before the label 7 at university is finalized.

Common misconceptions

• Mistakenly treating the first target label as final once it appears.
• Assuming that a single visible route already proves optimality without checking other unsettled branches.
• Believing that the algorithm terminates as soon as the destination is reached, rather than when the destination is the smallest uncircled vertex.

Watch the explanation

Explore next

• How is the actual shortest path recovered after the distance is found?
• What do the numbers written at the vertices represent in this algorithm demo?
• Why is vertex E processed before the destination is finalized?