# Floyd’s algorithm

Floyd’s algorithm^{} is also known as the all pairs shortest path algorithm. It will compute the shortest path between all possible pairs of vertices in a (possibly weighted) graph or digraph^{} simultaneously in $O({n}^{3})$ time (where $n$ is the number of vertices in the graph).

Algorithm Floyd(V)

Input: A weighted graph or digraph with vertices $V$

Output: A matrix $cost$ of shortest paths and a matrix $pred$ of predecessors in the shortest path

for $(a,b)\in {V}^{2}$ do

if $adjacent(a,b)$ then

$cost(a,b)\leftarrow weight(a,b)$

$pred(a,b)\leftarrow a$ else

$cost(a,b)\leftarrow \mathrm{\infty}$

$pred(a,b)\leftarrow null$

for $c\in V$ do

for $(a,b)\in {V}^{2}$ do

if $$ and $$ then

if $cost(a,b)=\mathrm{\infty}$ or $$ then

$cost(a,b)\leftarrow cost(a,c)+cost(c,b)$

$pred(a,b)\leftarrow pred(c,b)$

Title | Floyd’s algorithm |
---|---|

Canonical name | FloydsAlgorithm |

Date of creation | 2013-03-22 12:16:29 |

Last modified on | 2013-03-22 12:16:29 |

Owner | vampyr (22) |

Last modified by | vampyr (22) |

Numerical id | 6 |

Author | vampyr (22) |

Entry type | Algorithm |

Classification | msc 68R10 |

Classification | msc 05C38 |

Classification | msc 05C85 |

Synonym | all pairs shortest path algorithm |