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

Relevant Files:

Click here for build and run instructions