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)$