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