Graphs/Floyd Warshall

Notes

The Floyd-Warshall algorithm is an algorithm for computing the transitive closure G* of a graph G.

More generally, we can think of it as an algorithm for finding shortest paths in a graph. It works for weighted graphs, which can have positive or negative weights (unlike the Graphs/Dijkstra algorithm, which does not allow negative weights), but it cannot have negative weight cycles (that is, a cycle whose weights sum to a negative value).

The Floyd Warshall algorithm will find the lengths of the shortest paths between all pairs of vertices in $ O(n^3) \sim O(|V|^3) $ time.

The core idea of the algorithm is finding a shortest path from vertex i to vertex j that only utilizes a set of vertices labeled 1 to k. This is denoted shortestPath(i,j,k).

The base case, of k being 0, is when i and j are directly connected. Then the shortest path from i to j that does not pass through any other vertices is denoted:

shortestPath(i,j,0) = w(i,j)

where w(i,j) denotes the weight of the edge connecting vertex i to vertex j. From there, we can construct a new shortest path by taking the minimum of the shortest path passing through k, and the shortest path that goes from i to k-1 and then from k-1 to j:

shortestPath(i,j,k-1) = min( shortestPath(i,j,k) , shortestPath(i,k-1,j) + shortestPath(k-1,j,k) )

Pseudocode

def floyd_warshall(g):
	vertices = get list of vertices from g
	n = length of vertices
	gstar[0] = deep copy of g
	for k = 1..n:
		gstar[k] = deep copy of g[k-1]
		for i in 1..n:
			skip i=j and i=k
			for j in 1..n:
				skip j=k
				if edge(vertices[i],vertices[k]) in gstar[k-1] and edge(vertices[k],vertices[j]) in gstar[k-1]:
					add edge(vertices[i],vertices[j]) to gstar[k]
	return gstar[n]

Big O Cost

The cost of the Floyd Warshall algorithm is $ O(n^3) $

This is asymptotically the same as running a DFS on every node. However, this algorithm performs better for dense graphs or graphs represented with an adjacency matrix data structure.

References

Related

Graphs/Transitive Closure - the transitive closure of a directed graph can be found using the Floyd Warshall algorithm

Graphs/Dijkstra - related algorithm for finding the shortest paths between two vertices in a graph

Links

Link to Floyd Warshall entry in the NIST algorithms and data structures dictionary: https://xlinux.nist.gov/dads/HTML/floydWarshall.html