# Further Maths - Floyd's Algorithm

> Source: https://ollybritton.com/notes/a-level/further-maths/topics/floyds-algorithm/ · Updated: 2022-03-15 · Tags: school

## 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$??
![PHOTO INITIAL ROUTE TABLE](initial-route-table.png)

##### If there is no direct connection between two verticies 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.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt