The Floyd-Warshall algorithm is a shortest path algorithm for graphs. Like the Bellman-Ford algorithm or the Dijkstra's algorithm, it computes the shortest path in a graph. However, Bellman-Ford and Dijkstra are both single-source, shortest-path algorithms. This means they only compute the shortest path from a single source. Floyd-Warshall, 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, Floyd-Warshall 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.
Floyd-Warshall 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 Floyd-Warshall; no matter what house you're currently in, it will tell the fastest way to get to every other house.
The Floyd-Warshall 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.
Floyd-Warshall 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 Floyd-Warshall 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.
At the heart of Floyd-Warshall is this function:
This function returns the shortest path from to using the vertices from 1 to in the graph. The vertices are individually numbered .
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 and
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 and is the shortest known path, or it is the shortest known path from to some vertex (let's call it ) plus the shortest known path from to
Basically, what this function setup is asking this: "Is the vertex an intermediate of our shortest path (any vertex in the path besides the first or the last)?"
If is not an intermediate vertex, then the shortest path from to using the vertices in is also the shortest path using the vertices in
If is an intermediate vertex, then the path can be broken down into two paths, each of which uses the vertices in to make a path that uses all vertices in That is because the vertex is the middle point. This is illustrated in the image below.
The Floyd-Warshall algorithm can be described by the following pseudo code:
1 2 3 4 5 6 7 8 9 10 11 12 13
The Floyd-Warshall algorithm runs in 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.
Floyd-Warshall 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 Floyd-Warshall 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 Floyd-Warshall algorithm is best suited for dense graphs since it is not at all dependent on the number of edges. Performing Floyd-Warshall on a sparse graph erases its main benefit. For sparse graphs, Johnson's algorithm is more suitable.
The following implementation of Floyd-Warshall 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
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 dictionary--initialized on line 9--to represent the graph. Keys in this dictionary are vertex numbers and the values are a list of edges.
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
In general, Floyd-Warshall, 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
can be computed. is defined as the predecessor of vertex on a shortest path from vertex with all intermediate vertices in the set . So, for each iteration of the main loop, a new predecessor matrix is created.
The recursive formula for this predecessor matrix is as follows: