What is the rule for selecting the next vertex to process in Dijkstra's algorithm?

Conditions

• There are uncircled vertices with assigned distance labels.
• The algorithm is in the selection phase after updating neighbors.

Reasoning, step by step

1. Scan all uncircled vertices for their tentative distance labels.
2. Identify the smallest label among them.
3. Select the vertex corresponding to this smallest label.
4. Circle this vertex to mark it as settled.
5. Draw an arrow from its predecessor to record the path.
6. Proceed to update the neighbors of this newly settled vertex.

Example

In the video, after initializing home, the uncircled vertices are $A (2)$ and $C (3)$. The smallest is 2 at A, so A is circled. Later, among uncircled vertices $B (6)$, $C (3)$, $D (4)$, $E (4)$, the smallest is 3 at C, so C is circled. The speaker says: "Now we look for the smallest uncircled number that we've written on our graph. In this case it's two, so we're going to circle that..."

Common misconceptions

• Selecting the vertex with the largest distance.
• Selecting a vertex that is already circled.
• Ignoring the distance labels and choosing randomly.

Watch the explanation

Explore next

• How do you update the neighbors of the current circled vertex in Dijkstra's algorithm?
• Why does Dijkstra's algorithm not finalize the destination label 7 at university immediately when it first appears?
• What do the numeric labels and blue circles at the vertices represent in the Dijkstra's algorithm demonstration?