How do you handle multiple distance values at a single vertex during Dijkstra's algorithm?

Conditions

• A vertex is reachable via multiple paths from different circled vertices.
• New distance calculations are performed for an already labeled vertex.

Reasoning, step by step

1. Calculate the new tentative distance to the vertex from the current circled vertex.
2. Compare this new distance with the existing label at the vertex.
3. If the new distance is smaller, replace the old label with the new one and update the predecessor arrow.
4. If the new distance is larger or equal, cross out the new value and keep the existing smaller label.
5. Proceed to select the next smallest uncircled vertex.

Example

In the video, vertex C initially has a label 3 from home. When processing from A, a new distance of 4 is calculated ($2 + 2$). Since $4 > 3$, the value 4 is crossed out, and 3 remains as the valid distance for C. The speaker says: "Whenever we have two or more numbers at a vertex, we're going to cross out any number that isn't equal to the minimum."

Common misconceptions

• Leaving multiple distance values at a single vertex, leading to confusion.
• Updating the label with a larger value.
• Forgetting to cross out the larger value, which might be mistakenly selected later.

Watch the explanation

Explore next

• What do the numeric labels and blue circles at the vertices represent in the Dijkstra's algorithm demonstration?
• 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?