Dijkstra's algorithmEdexcel International A Level Maths: Flashcards

What these 12 flashcards ask

What does Dijkstra's algorithm find?
What three things are recorded in each vertex box?
What is the first step of Dijkstra's algorithm?
How do you choose the next vertex to label permanently?
How do you calculate a new working value?
When do you replace a working value?
How do you find the route after finishing?
Can the shortest route use a direct arc that is longer than a two-arc route?
When can Dijkstra's algorithm stop?
A road in the network closes. What do you do?
A new arc XY of weight x is added. When does it shorten the route from S to T?
What must be true of the arc weights for Dijkstra's algorithm?

Exam questions on Dijkstra's algorithm

A network has five vertices $S$ , $A$ , $B$ , $C$ and $T$ . The arcs and their lengths are $SA=9$ , $SB=5$ , $AB=3$ , $AC=10$ , $BC=2$ , $BT=9$ and $CT=6$ . Dijkstra's algorithm is applied starting at $S$ .
Find the shortest route from $S$ to $A$ and its length. Explain why the arc $SA$ is not used.2 marks
A network has six vertices $A$ to $F$ . The arcs and their lengths are $AB=2$ , $AC=8$ , $AD=9$ , $BC=13$ , $BE=5$ , $CD=13$ , $CE=14$ , $DF=6$ and $EF=4$ . Dijkstra's algorithm is applied starting at $A$ .
Find the shortest route from $A$ to $F$ and state its length.2 marks
A courier company has six depots $A$ to $F$ . The direct roads between depots and their lengths in km are $AB=4$ , $AC=3$ , $AD=11$ , $BC=10$ , $BE=5$ , $CD=13$ , $CE=7$ , $DF=13$ and $EF=12$ . A courier travels from $A$ to $F$ .
Use Dijkstra's algorithm to find the shortest route from $A$ to $F$ . State the order in which the vertices are permanently labelled, with their final labels, and the length of the route.3 marks

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).