FloydWarshall Algorithm
The FloydWarshall algorithm is a shortest path algorithm for graphs. Like the BellmanFord algorithm or the Dijkstra's algorithm, it computes the shortest path in a graph. However, BellmanFord and Dijkstra are both singlesource, shortestpath algorithms. This means they only compute the shortest path from a single source. FloydWarshall, on the other hand, computes the shortest distances between every pair of vertices in the input graph.
Imagine that you have 5 friends: Billy, Jenna, Cassie, Alyssa, and Harry. You know a few roads that connect some of their houses, and you know the lengths of those roads. But, FloydWarshall can take what you know and give you the optimal route given that information. For example, look at the graph below, it shows paths from one friend to another with corresponding distances.
FloydWarshall will tell the optimal distance between each pair of friends. It will clearly tell you that the quickest path from Alyssa's house to Harry's house is the connecting edge that has a weight of 1. But, it will also tell you that the quickest way to get from Billy's house to Jenna's house is to first go through Cassie's, then Alyssa's, then Harry's house before ending at Jenna's. This is the power of FloydWarshall; no matter what house you're currently in, it will tell the fastest way to get to every other house.
The FloydWarshall algorithm is an example of dynamic programming. It breaks the problem down into smaller subproblems, then combines the answers to those subproblems to solve the big, initial problem. The idea is this: either the quickest path from A to C is the quickest path found so far from A to C, or it's the quickest path from A to B plus the quickest path from B to C.
FloydWarshall is extremely useful in networking, similar to solutions to the shortest path problem. However, it is more effective at managing multiple stops on the route because it can calculate the shortest paths between all relevant nodes. In fact, one run of FloydWarshall can give you all the information you need to know about a static network to optimize most types of paths. It is also useful in computing matrix inversions.
Overview
At the heart of FloydWarshall is this function:
\[\text{ShortestPath}(i, j, k).\]
This function returns the shortest path from \(A\) to \(C\) using the vertices from 1 to \(k\) in the graph. The vertices are individually numbered \({1, 2, ..., k}\).
There is a base case and a recursive case. The base case is that the shortest path is simply the weight of the edge connecting \(A\) and \(C:\)
\[\text{ShortestPath}(i, j, 0) = \text{weight}(i, j).\]
The recursive case will take advantage of the dynamic programming nature of this problem. There are two possible answers for this function. Either the shortest path between \(i\) and \(j\) is the shortest known path, or it is the shortest known path from \(i\) to some vertex (let's call it \(z\)) plus the shortest known path from \(z\) to \(j:\)
\[\text{ShortestPath}(i, j, k) = \text{min}\big(\text{ShortestPath}(i, j, k), \text{ShortestPath}(i, k, k1) + \text{ShortestPath}(k, j, k1)\big).\]
Basically, what this function setup is asking this: "Is the vertex \(k\) an intermediate of our shortest path (any vertex in the path besides the first or the last)?"
If \(k\) is not an intermediate vertex, then the shortest path from \(i\) to \(j\) using the vertices in \(\{1, 2, ..., k1\}\) is also the shortest path using the vertices in \(\{1, 2, ..., k\}.\)
If \(k\) is an intermediate vertex, then the path can be broken down into two paths, each of which uses the vertices in \(\{1, 2, ..., k1\}\) to make a path that uses all vertices in \(\{1, 2, ..., k\}.\) That is because the vertex \(k\) is the middle point. This is illustrated in the image below.
Algorithm
The FloydWarshall algorithm can be described by the following pseudo code:
1 2 3 4 5 6 7 8 9 10 11 12 13 

The following picture shows a graph, \(G\), with vertices \(V = {A, B, C, D, E}\) with edge set \(E\). Some edge weights are shown, and others are not.
Also below is the resulting matrix \(D\) from the FloydWarshall algorithm. In this matrix, \(D[i][j]\) shows the distance between vertex \(i\) and vertex \(j\) in the graph. Solve for \(X\).
Complexity
The FloydWarshall algorithm runs in \(O\big(V^{3}\big)\) time. This is because of the three nested for
loops that are run after the initialization and population of the distance matrix, M.
See also: big O notation.
Average  
FloydWarshall  \(O(V^{3})\) 
FloydWarshall is completely dependent on the number of vertices in the graph. As you might guess, this makes it especially useful for a certain kind of graph, and not as useful for other kinds.
Is the FloydWarshall algorithm better for sparse graphs or dense graphs? (A sparse graph is one that does not have many edges connecting its vertices, and a dense graph has many edges.)
The FloydWarshall algorithm is best suited for dense graphs since it is not at all dependent on the number of edges. Performing FloydWarshall on a sparse graph erases its main benefit. For sparse graphs, Johnson's algorithm is more suitable. \(_\square\)
Sample Python Implementation
The following implementation of FloydWarshall is written in Python.
In this implementation, infinity is represented by a really large integer.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 

The Edge
class on line 1 is a simple object that holds information about the edge such as endpoints and weight. The vertex is just a simple integer for this implementation. The Graph
class uses a dictionaryinitialized on line 9to represent the graph. Keys in this dictionary are vertex numbers and the values are a list of edges.
The floydwarshall()
function on line 33 creates a matrix M
. It populates this matrix with shortest path information for each vertex. For example, the shortest path distance from vertex 0 to vertex 2 can be found at M[0][2]
.
Path Reconstruction
In general, FloydWarshall, at its most basic, only provides the distances between vertices in the resulting matrix. However, a simple change can allow the algorithm to reconstruct the shortest path as well. There are many different ways to do this, and all of them have their costs in memory. Speed is not a factor with path reconstruction because any time it takes to reconstruct the path will pale in comparison to the basic algorithm itself.
The most common way is to compute a sequence of predecessor matrices. During path calculation, even the matrices
\[P^{(0)}, P^{(1)}, ..., P^{(n)}\]
can be computed. \(P^{(k)}_{ij}\) is defined as the predecessor of vertex \(j\) on a shortest path from vertex \(i\) with all intermediate vertices in the set \(1, 2, ... , k\). So, for each iteration of the main loop, a new predecessor matrix is created.
The recursive formula for this predecessor matrix is as follows:
If \(i = j\) or \(\text{weight}(i, j) = \infty, P^{0}_{ij} = 0.\)
If \(i \neq j\) and \(\text{weight}(i, j) \lt \infty, P^{0}_{ij} = i.\)