Floyd-Warshall Shortest Path

Many researchers independently invented the Floyd-Warshall algorithm. They were:

Robert Floyd in 1962
Stephen Warshall in 1962
Peter Ingerman in 1962
Bernard Roy in 1959

The other algorithms in this section solve the single source shortest path problem; that is, calculating the distance between a single source vertex and every other vertex in a graph. This algorithms has the more lofty goal of computing the shortest path between all vertices. This is commonly known as the all-pairs shortest path problem. It returns $n^2$ solutions: a path for every vertex to every other vertex.

This algorithm is strikingly similar to Bellman-Ford. It works in the same way and has the same restrictions on negative cycles. Anyone with a good understanding of that algorithm will have no problems with this one. One thing to note is that Floyd-Warshall is NOT equivalent to running Bellman-Ford $n$ times as the asymptotic complexity is much better. However, in certain situations, it may be more efficient to execute a single source shortest path solution $n$ times. Assuming you are trying to solve the all-pairs shortest path problem, consider the following:

The Floyd-Warshall algorithm has an algorithmic complexity of $O(n^3)$ regardless of graph density.
Dijkstra’s algorithm solves the single source shortest path problem with the restriction that it cannot accommodate negative edge lengths. For a dense graph, executing Dijkstra’s algorithm $n$ times results in an overall runtime of $O(n^3\log_2 n)$ which is slightly higher thatn Floyd-Warshall. However, in the case of a spare graph, the resulting runtime is $O(n^2\log_2 n)$, which is a significant savings.
Executing Bellman Ford $n$ times works out to an algorithmic complexity of $O(n^2m)$. For a dense graph with $n^2$ vertices, that equates to $O(n^4)$ which is unthinkable. However, consider a sparse graph with less than $n$ vertices. In this case, the run time is lower than $O(n^3)$.

Solving the all-pairs shortest path problem for dense graphs with an algorithmic complexity lower than $O(n^3)$ is an open problem in computer science.

Applications

Internet Routing
Road Networks
Transitive Closure of a Binary Relation

Asymptotic Complexity

$O(n^3)$

Pseudo Code

inputs:
    G graph

solutions[graph->n + 1][graph->n][graph->n]

for every v in graph->V:
	for every w in graph->V:
		if v == w:
			solutions[0][v][w] = 0
		else if edge (v, w) existing in G:
			solutions[0][v][w] = (v, w)->weight
		else:
			solutions[0][v][w] = infinity

for k = 1 to graph->n:
	for v in graph->V:
		for w in graph->V:
			solutions[k] = minimum(solutions[k - 1][v][w], 
					(solutions[k - 1][v][k] + solutions[k - 1][k][w]))

for v in graph->n:
	if solutions[graph->n][v][v] < 0:
		return "negative cycle detected"

return solutions[graph->n]

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions