How do you update the neighbors of the current circled vertex in Dijkstra's algorithm?

Conditions

• There is a current circled (settled) vertex.
• The vertex has neighbors that are not yet circled.
• Edge weights are known and non-negative.

Reasoning, step by step

1. Identify the current circled vertex and its distance label.
2. List all neighbors of this vertex that are not yet circled.
3. For each unvisited neighbor, add the edge weight to the current vertex's distance.
4. Write the resulting sum as a tentative label next to the neighbor.
5. If the neighbor already had a label, compare the new sum with the old label.
6. Keep the smaller value and cross out the larger one if necessary.
7. Draw a predecessor arrow from the current vertex to the neighbor if the label is updated.

Example

In the video, from the circled vertex 'home' (distance 0), the neighbors A and C are updated. The edge weight to A is 2, so $0 + 2 = 2$ is written at A. The edge weight to C is 3, so $0 + 3 = 3$ is written at C. Later, from A (distance 2), B is updated: $2 + 4 = 6$.

Common misconceptions

• Adding the edge weight to the neighbor's existing label instead of the current vertex's label.
• Updating neighbors that are already circled.
• Forgetting to compare with existing labels and simply overwriting them.

Watch the explanation

Explore next

• What is the initialization step for Dijkstra's algorithm in the home-to-university example?
• How do you handle multiple distance values at a single vertex during Dijkstra's algorithm?
• What do the numeric labels and blue circles at the vertices represent in the Dijkstra's algorithm demonstration?