Dijkstra's algorithm

Dijkstra's algorithm Flashcards

Spec 2.2 · Edexcel International A Level Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 12 cards
What does Dijkstra's algorithm find?
The shortest distance from a start vertex to every other vertex, labelled in order of increasing distance.
What three things are recorded in each vertex box?
The order of labelling, the final value and the working values.
What is the first step of Dijkstra's algorithm?
Give the start vertex order 1 and final value 00.
How do you choose the next vertex to label permanently?
Choose the unlabelled vertex with the smallest working value.
How do you calculate a new working value?
Final value of the vertex just labelled plus the arc weight to the neighbour.
When do you replace a working value?
Only when the new value is smaller than the one already there.
How do you find the route after finishing?
Back-track from the target: choose the neighbour whose final value equals this vertex's final value minus the arc weight.
Can the shortest route use a direct arc that is longer than a two-arc route?
No. Compare the working values: the smaller one gives the final value.
When can Dijkstra's algorithm stop?
When the target vertex has been permanently labelled.
A road in the network closes. What do you do?
Remove the arc and apply the algorithm again.
A new arc XYXY of weight xx is added. When does it shorten the route from SS to TT?
When d(S,X)+x+d(Y,T)d(S,X)+x+d(Y,T) is less than the current shortest length.
What must be true of the arc weights for Dijkstra's algorithm?
They must be positive, such as distances, times or costs.

Flashcards