What does Dijkstra's algorithm find?

Dijkstra's algorithm finds the shortest distance from a single fixed start vertex to every other vertex in a network. It is used in practice to reduce the time, cost or distance between two points.

What three things are recorded in the labelling box at each vertex?

Each box records the order of labelling , the final label and the working values . The final label is that vertex's shortest distance from the start, and the last working value written there always becomes it.

How is the start vertex labelled in Dijkstra's algorithm?

The start vertex is given 1 in its order of labelling box and 0 in its final label box. The 0 records that its distance from itself is zero.

Which vertex is given its final label next in Dijkstra's algorithm?

The next vertex finalised is the one with the smallest working value among all those that do not yet have a final label. Its current working value is copied into its final label box, and it takes the next number in the order of labelling.

How is the shortest path itself found once every vertex has a final label?

Work backwards from the destination: two vertices lie on the path when the difference between their final labels equals the weight of the edge joining them. So final labels of 15 and 8 at vertices joined by an edge of weight 7 put both of them on the path.

True or False? Once a vertex has been given its final label, that label can still be reduced later.

False. A final label is permanent, which is why it is sometimes called a permanent label . Only the working values at a vertex change, and they stop changing once its final label has been written.

When can Dijkstra's algorithm be stopped early?

The algorithm can stop as soon as the destination vertex has had its final label completed. There is then no need to label the rest of the network, which is a real saving on a large one.

What does Floyd's algorithm find?

Floyd's algorithm finds the shortest distance and the shortest route between every pair of vertices in a network. It does this by setting up two matrices and updating both at each iteration.

Which two matrices does Floyd's algorithm use?

Floyd's algorithm uses a distance matrix , holding the shortest distance found so far between each pair of vertices. It also uses a route matrix , from which the shortest route between any pair can be read off at the end.

How is the route matrix updated during an iteration of Floyd's algorithm?

Wherever a cell in the distance matrix was updated, the matching cell in the route matrix changes to the vertex of the highlighted column . Cells whose distance did not change are left exactly as they were.

How many iterations does Floyd's algorithm take?

One for each vertex in the network, so a network with five vertices takes five iterations. An iteration that changes nothing still counts, and later iterations can still make changes, so an empty one is not a signal to stop.

How do you read the shortest route between two vertices from the final route matrix?

Start on the row of the starting vertex and look at the cell under the destination column. Move to the row of the vertex named there and repeat, until that cell holds the destination itself.

True or False? In an undirected network, every distance matrix in Floyd's algorithm stays symmetrical.

True. The distance from one vertex to another is the same in both directions, so the symmetry survives every iteration. That halves the work and acts as a check on each stage.

A power station is fixed and you need the shortest route from it to every other point. Which algorithm suits?

Dijkstra's algorithm , because it works outwards from a single fixed starting vertex. Floyd's algorithm would suit a case where the starting point could be anywhere, such as a robot inspecting a network of pipelines.

What is the advantage and the disadvantage of Dijkstra's algorithm?

Its advantage is speed , since it can be stopped as soon as the destination has been reached. Its disadvantage is the limited information it gives, covering only routes from the one starting vertex.

What is the advantage and the disadvantage of Floyd's algorithm?

Its advantage is the amount of information it gives, covering every pair of vertices at once. Its disadvantage is the time it takes, especially when it is being carried out by hand.

True or False? Running Dijkstra's algorithm once from every vertex gives the same information as Floyd's algorithm.

True. Each run gives the shortest distances from one starting vertex, so doing it for every vertex in turn covers every pair. Floyd's algorithm reaches the same result in a single process instead of many separate ones.

What do Dijkstra's and Floyd's algorithms have in common?

Both find the shortest path between vertices in a network, and the weight of that path. Everything else about them, including how much of the network they cover, is different.

A LevelFurther MathsEdexcelDecision 1FlashcardsAlgorithms on GraphsShortest Path Algorithms

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

Exam code: 9FM0

1/21

0Still learning

Know0

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

Was this flashcard helpful?

Cards in this collection (21)

What does Dijkstra's algorithm find?
Dijkstra's algorithm finds the shortest distance from a single fixed start vertex to every other vertex in a network.
It is used in practice to reduce the time, cost or distance between two points.
What three things are recorded in the labelling box at each vertex?
Each box records the order of labelling, the final label and the working values.
The final label is that vertex's shortest distance from the start, and the last working value written there always becomes it.
How is the start vertex labelled in Dijkstra's algorithm?
The start vertex is given 1 in its order of labelling box and 0 in its final label box.
The 0 records that its distance from itself is zero.
Complete the rule for a new working value in Dijkstra's algorithm:
$working value = final label +______$
The completed rule is:
$working value = final label + edge weight$
A new working value replaces one already at a vertex only if it is smaller.
Which vertex is given its final label next in Dijkstra's algorithm?
The next vertex finalised is the one with the smallest working value among all those that do not yet have a final label.
Its current working value is copied into its final label box, and it takes the next number in the order of labelling.
How is the shortest path itself found once every vertex has a final label?
Work backwards from the destination: two vertices lie on the path when the difference between their final labels equals the weight of the edge joining them.
So final labels of 15 and 8 at vertices joined by an edge of weight 7 put both of them on the path.
True or False?
Once a vertex has been given its final label, that label can still be reduced later.
False.
A final label is permanent, which is why it is sometimes called a permanent label.
Only the working values at a vertex change, and they stop changing once its final label has been written.
When can Dijkstra's algorithm be stopped early?
The algorithm can stop as soon as the destination vertex has had its final label completed.
There is then no need to label the rest of the network, which is a real saving on a large one.
What does Floyd's algorithm find?
Floyd's algorithm finds the shortest distance and the shortest route between every pair of vertices in a network.
It does this by setting up two matrices and updating both at each iteration.
Which two matrices does Floyd's algorithm use?
Floyd's algorithm uses a distance matrix, holding the shortest distance found so far between each pair of vertices.
It also uses a route matrix, from which the shortest route between any pair can be read off at the end.
How are the two matrices set up before Floyd's algorithm begins?
The initial distance matrix holds the direct distances, with $\infty$ wherever there is no direct link between a pair.
The initial route matrix assumes every shortest route is the direct one, so each column is filled throughout with its own vertex letter.
What happens in the $k$ th iteration of Floyd's algorithm?
Highlight the $k$ th row and the $k$ th column of the distance matrix, then compare every other cell with the sum of the two highlighted values in its own row and column.
Where that sum is smaller, the cell is updated.
How is the route matrix updated during an iteration of Floyd's algorithm?
Wherever a cell in the distance matrix was updated, the matching cell in the route matrix changes to the vertex of the highlighted column.
Cells whose distance did not change are left exactly as they were.
How many iterations does Floyd's algorithm take?
One for each vertex in the network, so a network with five vertices takes five iterations.
An iteration that changes nothing still counts, and later iterations can still make changes, so an empty one is not a signal to stop.
How do you read the shortest route between two vertices from the final route matrix?
Start on the row of the starting vertex and look at the cell under the destination column.
Move to the row of the vertex named there and repeat, until that cell holds the destination itself.
True or False?
In an undirected network, every distance matrix in Floyd's algorithm stays symmetrical.
True.
The distance from one vertex to another is the same in both directions, so the symmetry survives every iteration.
That halves the work and acts as a check on each stage.
A power station is fixed and you need the shortest route from it to every other point. Which algorithm suits?
Dijkstra's algorithm, because it works outwards from a single fixed starting vertex.
Floyd's algorithm would suit a case where the starting point could be anywhere, such as a robot inspecting a network of pipelines.
What is the advantage and the disadvantage of Dijkstra's algorithm?
Its advantage is speed, since it can be stopped as soon as the destination has been reached.
Its disadvantage is the limited information it gives, covering only routes from the one starting vertex.
What is the advantage and the disadvantage of Floyd's algorithm?
Its advantage is the amount of information it gives, covering every pair of vertices at once.
Its disadvantage is the time it takes, especially when it is being carried out by hand.
True or False?
Running Dijkstra's algorithm once from every vertex gives the same information as Floyd's algorithm.
True.
Each run gives the shortest distances from one starting vertex, so doing it for every vertex in turn covers every pair.
Floyd's algorithm reaches the same result in a single process instead of many separate ones.
What do Dijkstra's and Floyd's algorithms have in common?
Both find the shortest path between vertices in a network, and the weight of that path.
Everything else about them, including how much of the network they cover, is different.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:Minimum Spanning TreesNext:The Route Inspection Algorithm