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.
- Internet Routing
- Road Networks
- Transitive Closure of a Binary Relation
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[v][w] = 0 else if edge (v, w) existing in G: solutions[v][w] = (v, w)->weight else: solutions[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]
Click here for build and run instructions