What do the numeric labels and blue circles at the vertices represent in the Dijkstra's algorithm demonstration?
The numeric labels at the vertices represent the current best known distance from the source vertex (home) to that specific vertex. A blue circle around a label indicates that this distance has been accepted as final for that vertex in the current run of the algorithm. Uncircled numbers remain tentative candidates that can still be improved or compared as the algorithm processes other vertices.
Conditions
- The demonstration uses a visual whiteboard-style representation.
- The source vertex is 'home'.
- The algorithm is Dijkstra's shortest path algorithm.
Reasoning, step by step
- Observe the numbers written next to each vertex.
- Interpret these numbers as distances from the source 'home'.
- Identify the blue circles drawn around some numbers.
- Interpret the circles as markers indicating that the vertex has been selected/settled.
- Understand that uncircled numbers are tentative and may change.
- Recognize that circled numbers are final and will not change.
Example
In the video, vertex A has a circled label 2, meaning the shortest distance from home to A is finalized as 2. Vertex E initially has an uncircled label 4, which is later circled, meaning 4 is confirmed as the shortest distance to E. The speaker refers to "uncircled vertex" and compares labels like 7 and 9.
Common misconceptions
- Assuming the numbers represent the vertex ID or name.
- Thinking that uncircled numbers are final and cannot be changed.
- Believing that the circles indicate the order in which vertices were visited, rather than their settled status.
Watch the explanation
2:00 – 4:00Watch this moment ↗
Explore next
Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.