What does Dijkstra's algorithm find?

The shortest distance between two vertices of a network, together with the route that achieves it. Run across a whole network it gives the shortest distance from one fixed start vertex to every other vertex.

What does a 'working value' at a vertex represent?

A working value is the shortest distance to that vertex found so far , along whichever routes have been explored up to that point. It is provisional, and a vertex may collect several working values as the algorithm goes on.

Define the final label of a vertex in Dijkstra's algorithm.

The final label of a vertex is the shortest distance from the start vertex to that vertex, along the best route through the network. Every vertex ends up with one, and together they are what the algorithm was run to produce.

A vertex already has a working value, and a new route reaches it with another. When do you write the new one in?

Only when the new value is smaller than the one already there. A working value records the best distance found so far, so a larger figure tells you nothing and is simply not written down.

Several vertices have working values but no final label yet. Which one is made final next?

The one carrying the smallest working value anywhere in the network. That working value becomes its final label, and the vertex takes the next number in the labelling order.

True or False? In Dijkstra's algorithm, a vertex's final label can be improved later if a shorter route to it is found.

False. A final label is permanent, which is why it is sometimes called a permanent label instead. The algorithm only makes a vertex final when nothing still unexplored could possibly reach it more cheaply, so there is never anything left to improve.

Every vertex now has its final label. How do you read off the shortest route itself?

Work backwards from the destination towards the start vertex. Two vertices lie on the shortest route when the difference between their final labels is exactly equal to the weight of the edge joining them.

International A Level (IAL)MathsEdexcelDecision 1FlashcardsAlgorithms on GraphsShortest Path Algorithms

Shortest Path Algorithms (Edexcel International A Level (IAL) Maths: Decision 1): Flashcards

Exam code: YMA01

1/10

0Still learning

Know0

FrontDijkstra's Algorithm
What does Dijkstra's algorithm find?

Was this flashcard helpful?

Cards in this collection (10)

What does Dijkstra's algorithm find?
The shortest distance between two vertices of a network, together with the route that achieves it.
Run across a whole network it gives the shortest distance from one fixed start vertex to every other vertex.
What does a 'working value' at a vertex represent?
A working value is the shortest distance to that vertex found so far, along whichever routes have been explored up to that point.
It is provisional, and a vertex may collect several working values as the algorithm goes on.
Define the final label of a vertex in Dijkstra's algorithm.
The final label of a vertex is the shortest distance from the start vertex to that vertex, along the best route through the network.
Every vertex ends up with one, and together they are what the algorithm was run to produce.
How is the start vertex labelled at the beginning of Dijkstra's algorithm?
It is given labelling order $1$ and a final label of $0$ .
The zero is right because the shortest distance from the start vertex to itself is no distance at all.
A vertex already has a working value, and a new route reaches it with another. When do you write the new one in?
Only when the new value is smaller than the one already there.
A working value records the best distance found so far, so a larger figure tells you nothing and is simply not written down.
Several vertices have working values but no final label yet. Which one is made final next?
The one carrying the smallest working value anywhere in the network.
That working value becomes its final label, and the vertex takes the next number in the labelling order.
True or False?
In Dijkstra's algorithm, a vertex's final label can be improved later if a shorter route to it is found.
False.
A final label is permanent, which is why it is sometimes called a permanent label instead.
The algorithm only makes a vertex final when nothing still unexplored could possibly reach it more cheaply, so there is never anything left to improve.
Complete the fact about stopping Dijkstra's algorithm early:
The algorithm may be stopped as soon as the $______$ vertex has been given its final label, which saves a good deal of work on a large network.
The completed fact is:
The algorithm may be stopped as soon as the destination vertex has been given its final label, which saves a good deal of work on a large network.
There is no need to settle every vertex when only one destination has been asked for.
Every vertex now has its final label. How do you read off the shortest route itself?
Work backwards from the destination towards the start vertex.
Two vertices lie on the shortest route when the difference between their final labels is exactly equal to the weight of the edge joining them.
Two adjacent vertices have final labels $8$ and $15$ , and the edge joining them has weight $7$ . Do they lie on the shortest route?
They do lie on it.
The difference $15 - 8 = 7$ matches the weight of that edge exactly, which is the test for an edge belonging to the shortest route.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:Minimum Spanning TreesNext:The Route Inspection Algorithm