Floyd-Warshall algorithm

Floyd-Warshall algorithm try to find the shortest path among all the vertices from a graph, with positive or negative weighted edges. It's best suited for denses graphs.

Another way to illustrate it is to run the Dijkstra algorithm for all the vertices in the graph.

Complexity

Time complexity

• Worst-case: $O(|V{|}^3)$
• Best-case: $\mathrm{\Omega }(|V{|}^3)$
• Average-case: $\mathrm{\Theta }(|V{|}^3)$

Space complexity

• Worst-case: $O(|V|{)}^2$

Note: if you repeat $|V|$ time the Dijkstra algorithm instead, the complexity become $O(|V{|}^2\log |V|+|V||E|)$. It's better, but it works only with positive weighted edges.

Resources

• Floyd-Warshall in 4 minutes – Youtube