# 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\infty$

$pred(a,b)\leftarrow null$

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

if $cost(a,c)<\infty$ and $cost(c,b)<\infty$ then

if $cost(a,b)=\infty$ or $cost(a,c)+cost(c,b) then

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

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

Title Floyd’s algorithm FloydsAlgorithm 2013-03-22 12:16:29 2013-03-22 12:16:29 vampyr (22) vampyr (22) 6 vampyr (22) Algorithm msc 68R10 msc 05C38 msc 05C85 all pairs shortest path algorithm