Dijkstra's algorithm

Dijkstra's algorithm Flashcards

Spec 2.2 · Edexcel A-Level Further 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 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 XX?
Add the shortest distance from start to XX and the shortest distance from XX 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.

Flashcards