Floyd's algorithm

Floyd's algorithm is a O(n^3) algorithm to find the shortest path between all pairs of nodes in a graph. It was developed by Robert W Floyd.

This algorithm is designed to find the least-expensive paths between all the vertices in a graph. It does this by operating on a matrix representing the costs of edges between vertices. Before we invoke Floyd's algorithm we must build a matrix, usually in a two-dimensional array. If there are n vertices in our graph, our matrix will be nxn. Each row in the matrix represents a "starting" vertex in the graph while each column in the matrix represents an "ending" point in the graph. If there is an edge between a starting point i and ending point j in the graph, the cost of this edge is placed in position (i,j) of the matrix. If we are dealing with an undirected graph in which all edges are bi-directional, an entry is also made in position (j,i) of the matrix. If there is no edge directly linking two vertices, an infinite (or, in practice, very large) value is placed in the (i,j) position of the matrix to specify that it is impossible to directly move from i to j.

For example, if we have a graph in which points 1 and 5 are connected by a bi-directional edge with a cost of 22 units, we would place the number 22 into positions (1,5) and (5,1) of our matrix.

Once we have set this matrix up, we use Floyd's algorithm to compute the shortest distance between all points in the graph.

Implementation

Floyd's algorithm is given below in C:

int floyds(int *matrix) {

 int k, i, j;

 for (k = 1; k <= n; k++)
   for (i = 1; i <= n; i++)
     for (j = 1; j <= n; j++)
       if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))
         matrix[i,j] = matrix[i][k] + matrix[k][j];

}

When this routine finishes the entries in all positions of the matrix represent the lowest-cost traversal between the row-vertex and column-vertex.

Floyd's algorithm works by looking for all non-direct paths between two vertices that have a less-expensive total cost than the best way yet found to move between said vertices. If such a path is found, it becomes the value against which future indirect paths between these vertices are tested. In the end, each element of the matrix represents the lowest-cost traversal between the vertices it's row and column represent. Remember that if the graph is directed, so is the answer in (i,j) of the matrix; moreover, (i,j) may not be equal to (j,i) in a di-graph.

It is clear that Floyd's algorithm takes n3 time.

See also

Implementation