What is the initialization step for Dijkstra's algorithm in the home-to-university example?
The initialization step involves assigning a distance of 0 to the starting vertex (home) and marking it as visited by drawing a circle around it. All other vertices are initially considered to have an infinite or undefined distance until they are updated by neighbor calculations. This sets the baseline for the shortest path computation.
Conditions
- The algorithm is starting.
- The source vertex is identified as 'home'.
Reasoning, step by step
- Identify the source vertex ('home').
- Write the number 0 next to the source vertex.
- Draw a circle around the 0 to mark the vertex as visited/settled.
- Prepare to update the neighbors of the source vertex in the next step.
Example
The video states: "To start off with, what we're going to do is next to the vertex home, we're going to put a zero because it is zero distance from home, and we're going to circle that vertex." A blue '0' is written next to 'home', and a blue circle is drawn around it.
Common misconceptions
- Starting with a distance of 1 or another non-zero value for the source.
- Forgetting to circle the source vertex.
- Assuming all vertices start with a distance of 0.
Watch the explanation
0:15 – 0:27Watch this moment ↗
Explore next
- How do you update the neighbors of the current circled vertex in Dijkstra's algorithm?
- 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?
Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.