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

Links

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

Flags

Graphs/Floyd Warshall

From charlesreid1

Contents