What is stored in each vertex box?

Vertex, order of labelling, final label and working values.

What is a working value?

A temporary distance at a vertex that is replaced if a smaller one is found.

How is the next permanent label chosen?

The smallest working value among all vertices not yet permanently labelled.

What do you do if a new route to a vertex is shorter?

Replace the working value with the smaller one and cross out the old.

When does the algorithm stop for one target?

When the target receives a permanent label.

How do you find the route after labelling?

Work back from the target: choose the neighbour whose label plus edge length equals the current label.

Why is the smallest working value final?

Any other route goes through a vertex with a larger working value, and weights are not negative.

How do you find the shortest route through a given vertex X?

Add the shortest distance from start to X and the shortest distance from X to the target.

What happens to labels when a road closes?

Labels of vertices whose routes do not use the closed road are unchanged; recalculate from where it mattered.

In a directed network, which edges are used?

Only arcs followed in the direction of their arrows.

Dijkstra's algorithmEdexcel A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What does Dijkstra's algorithm find?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What does Dijkstra's algorithm find?: The shortest path from a start vertex to the other vertices of a network with non-negative weights.
What is stored in each vertex box?: Vertex, order of labelling, final label and working values.
What is a working value?: A temporary distance at a vertex that is replaced if a smaller one is found.
What is the label of the start vertex?: 0, with order of labelling 1.
How is the next permanent label chosen?: The smallest working value among all vertices not yet permanently labelled.
What do you do if a new route to a vertex is shorter?: Replace the working value with the smaller one and cross out the old.
When does the algorithm stop for one target?: When the target receives a permanent label.
How do you find the route after labelling?: Work back from the target: choose the neighbour whose label plus edge length equals the current label.
Why is the smallest working value final?: Any other route goes through a vertex with a larger working value, and weights are not negative.
How do you find the shortest route through a given vertex $X$ ?: Add the shortest distance from start to $X$ and the shortest distance from $X$ to the target.
What happens to labels when a road closes?: Labels of vertices whose routes do not use the closed road are unchanged; recalculate from where it mattered.
In a directed network, which edges are used?: Only arcs followed in the direction of their arrows.

Exam questions on Dijkstra's algorithm

A road network joins a depot $S$ to a warehouse $T$ through four junctions $A$ , $B$ , $C$ and $D$ . The roads and their lengths in km are $SA=4$ , $SB=7$ , $AB=2$ , $AC=6$ , $BC=3$ , $BD=8$ , $CD=6$ , $CT=8$ and $DT=4$ . Dijkstra's algorithm is used to find the shortest route from $S$ to $T$ .
Explain why the final label at $B$ is 6 and not 7.2 marks
Six towns $A$ to $F$ are joined by roads with lengths in km: $AB=5$ , $AC=8$ , $BC=2$ , $BD=9$ , $CD=4$ , $CE=9$ , $DE=3$ , $DF=10$ and $EF=6$ . Dijkstra's algorithm is used starting from $A$ .
Use the labels to find the shortest route from $A$ to $F$ and show how you worked it out.2 marks
A courier network has seven vertices $S$ , $A$ , $B$ , $C$ , $D$ , $X$ and $T$ . The roads and their lengths in km are $SA=8$ , $SC=12$ , $AC=3$ , $AX=11$ , $BC=2$ , $BD=6$ , $BT=10$ , $CD=7$ , $CT=5$ , $DX=9$ and $XT=4$ .
Apply Dijkstra's algorithm from $S$ . Show the working values at $C$ , and state the permanent labels of the next three vertices to be labelled after $S$ .3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).