Floyd's Algorithm
Floyd's Algorithm
Method
- Complete an initial distance table with only nodes that connect, if there is no direct route, then replace with an infinity symbol
- Complete an initial route table
- In the first iteration, copy the first row and first column into a new table and shade these values lightly
- Consider each unshaded box in turn and match it up with the values on the shaded row and column
- If the box and column values that correspond to the unshaded value are less, then update the value in the new table with brackets around it
- Repeat for the second row and column
[Floyd's Algorithm(/a-level/further-maths/further-decision-1/algorithms-on-graphs/floyd-s-algorithm.html)
| - | 7 | 10 | \(\infty\) | 14 |
|-----------|-----------|----|-----------|-----------|
| 7 | - | 19 | 11 | \(\infty\) |
| \(\infty\) | 19 | - | 24 | \(\infty\) |
| \(\infty\) | 11 | 24 | - | 1 |
| 10 | \(\infty\) | 17 | 1 | - |