Further Maths - Floyd's Algorithm

Flashcards

What is Floyd’s algorithm used for?

Finding the shortest distance between any two vertices on a network.

What is the advantage of Floyd’s algorithm over Dijkstra’s?

It can find the shortest distance between _ any _ two vertices, not the shortest distance to one specific vertex.

What two things do you need to set up at the start of Floyd’s algorithm?

What would you fill a route table with initially for vertices $ABCD$?

If there is no direct connection between two vertices when filling out the distance table in Floyd’s algorithm, what should you put?

\[\infty\]

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.