Further Maths - Floyd's Algorithm
Flashcards
2022-03-15
What is Floyd’s algorithm used for?
Finding the shortest distance between any two verticies on a network.
What is the advantage of Floyd’s algorithm over Dijkstra’s?
It can find the shortest distance between any two verticies, not the shortest distance to one specific vertex.
What two things do you need to set up at the start of Floyd’s algorithm?
- Distance table
- Route table
What would you fill a route table with initially for verticies $ABCD$?
If there is no direct connection between two verticies when filling out the distance table in Floyd’s algorithm, what should you put?
What do you highlight in Floyd’s algorithm at each iteration?
A row and a column.
What do you do if the sum of the corresponding highlighted row and column is smaller than the current cell in Floyd’s algorithm?
Replace the distance.
In the 2nd iteration of Floyd’s algorithm, what do you do to the corresponding cell of a route table if you’ve just updated a distance table?
Replace it with the vertex in column 2 of the same row.