Dijkstra's algorithm

Dijkstra's algorithm Quiz

Spec 2.2 · Edexcel International A Level Maths: Quiz

Studying this course? Keep your progress in one place.

Pick an answer for each. Quizzes never use energy.

5 questions, one answer each

Each answer is checked as you go, with why.

See all 5 questions

1. In Dijkstra's algorithm, vertex $A$ has final value $7$ and the arc $AB$ has weight $4$ . $B$ has a working value of $13$ . What happens?
- A. $B$ keeps $13$
- B. $B$ is given a working value of $11$
- C. $B$ is permanently labelled $4$
- D. $B$ is given a working value of $3$
2. Which vertex is permanently labelled next?
- A. The one with the largest working value
- B. The one nearest the target
- C. The one joined to the start by the shortest arc
- D. The one with the smallest working value that is not yet labelled
3. In a network, final values are $S=0$ , $A=5$ , $B=8$ and the arcs are $SA=5$ , $AB=3$ , $SB=9$ . What is the shortest route to $B$ ?
- A. $S$ - $B$ of length $9$
- B. $S$ - $A$ - $B$ of length $8$
- C. $S$ - $A$ - $B$ of length $9$
- D. $S$ - $B$ of length $8$
4. The final value at $T$ is $20$ . The arc $UT$ has weight $6$ . Which final value at $U$ means $U$ is on the shortest route?
- A. $26$
- B. $6$
- C. $14$
- D. $13$
5. Which statement about Dijkstra's algorithm is true?
- A. It finds the shortest route only to the target
- B. It uses arc weights that can be negative
- C. It finds the shortest distance to every vertex
- D. It starts at the vertex with the largest arc