Floyd's Algorithm (Edexcel A-Level Further Mathematics): Flashcards

Shortest paths between all pairs of nodes

Dense graphs

Cannot handle negative weight cycles

Distance matrix and route matrix

$0$

$infty$ (infinity)

$d[i][j] = min(d[i][j], d[i][k] + d[k][j])$

Intermediate node

$n$ iterations

Node used to travel directly from $i$ to $j$