What is the final shortest distance from home to university in the worked example?

Conditions

• The algorithm has processed all vertices with tentative labels smaller than 7.
• The label 7 at university is the smallest remaining uncircled label.
• The graph edge weights are fixed as shown in the example.

Reasoning, step by step

1. Process vertex E (label 4): Calculate candidate for university as $4 + 5 = 9$. Cross out 9 because $9 > 7$.
2. Process vertex B (label 6): Calculate candidate for university as $6 + 2 = 8$. Cross out 8 because $8 > 7$.
3. Check for remaining uncircled vertices with labels < 7. None exist.
4. Circle the label 7 at university as the final shortest distance.
5. State the result: The shortest distance from home to university is 7.

Example

The video states: "And now finally we've got this seven here is the smallest uncircled vertex ... that tells us that the shortest distance from home to university is seven." The number 7 is circled at the university vertex.

Common misconceptions

• Assuming the first candidate label seen at the destination is the final answer.
• Forgetting to process all smaller uncircled vertices before finalizing the destination.
• Confusing the tentative label with the final settled distance.

Watch the explanation

Explore next

• Why does Dijkstra's algorithm not finalize the destination label 7 at university immediately when it first appears?
• How do you reconstruct the shortest path from home to university after running Dijkstra's algorithm?
• What do the numbers written at the vertices represent in this algorithm demo?