Floyd’s algorithm

Floyd’s algorithmMathworldPlanetmath 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 digraphMathworldPlanetmath simultaneously in O(n3) 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)V2 do
          if adjacent(a,b) then


pred(a,b)a else



for cV do
          for (a,b)V2 do

if cost(a,c)< and cost(c,b)< then

if cost(a,b)= or cost(a,c)+cost(c,b)<cost(a,b) then



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