Dijkstra's algorithm Quiz

1. The working values at three unlabelled vertices are 9, 7 and 12. Which is made permanent?

• A. $9$
• B. $12$
• C. $7$
• D. None yet

2. $X$ has label 10 and road $XY=4$. $Y$ has working value 15. What happens?

• A. $Y$ keeps 15
• B. $Y$ is replaced by 19
• C. $Y$ is replaced by 14
• D. $Y$ is made permanent as 14 at once

3. How do you find the shortest route after the labels are known?

• A. Join the vertices in order of labelling
• B. Choose the smallest edges from the start
• C. Add every edge length
• D. Work back from the target through vertices whose label plus edge length gives the current label

4. Roads: $SA=3$, $SB=5$, $AB=1$, $AT=7$, $BT=4$. What is the shortest distance from $S$ to $T$?

• A. $8$
• B. $9$
• C. $10$
• D. $7$

5. When can the algorithm stop if only the shortest route to $T$ is needed?

• A. When $T$ first gets a working value
• B. When $T$ is given a permanent label
• C. When all edges have been used
• D. When every working value has been crossed out