Floyd Warshall algorithm is an All-Pairs shortest path algorithm. This means it calculates the value of the shortest path between each pair of nodes in a graph.

The most important questions are:

1: What are the main differences between Floyd Warshall and Dijkstra?

• Floyd Warshall algorithm is a Dynamic Programming based algorithm. The technique used in this algorithm is known as Matrix Chain Multiplication. A shortest path between 2 nodes in a graph would be a chain of nodes.
• Floyd Warshall algorithm runs in O(V^3) where V is the number of nodes in our graph.
• Since there isn’t a more efficient implementation for sparse graphs, other shortest path algorithms are often better suited for sparse graphs.

2: Why don’t we make Dijkstra from each node in our graph and forget about Floyd Warshall?

• For simple problems and applications of Floyd Warshall algorithm, its implementation is very short (5-6 lines of code). Hence, if O(V^3) is good enough, then Floyd Warshall is preferable.
• Floyd Warshall can detect the existence of negative cycles in the graph.
• There are a lot of advanced applications of Floyd Warshall algorithm that Dijkstra cannot be used for. In fact, this is true with most algorithms and contests. We don’t only use the algorithm, but once we understand why and how the algorithm works, a lot of problems can be solved with a similar approach.

3: What are some examples of applications of Floyd Warshall algorithm that Dijkstra cannot handle?

• Find the shortest path between 2 nodes with a restriction that we should traverse exactly L edges (where L is a huge number like 10^9). Of course, the question only makes sense when we are allowed to traverse the same edge more than once.
• Find a negative cycle in a weighted graph with minimum number of edges forming this cycle (the total weight doesn’t matter) it should just be negative and the number of edges is minimum.
• Often, you will notice that Floyd Warshall technique can be applied when we need to work with the adjacency matrix representation of a graph.

Video Tutorial - I

Although the implementation of Floyd Warshall is quite simple, it’s not straightforward to understand. I recommend watching the MIT lecture about all pairs shortest paths to ensure a deep understanding of this algorithm (till 57 mins, before Johnson’s algorithm). However, I have included a shorter tutorial that does a good job if your prefer that.

Video Tutorial - II

Further reading

1. Here is a text tutorial on the algorithm on WCIPEG: Floyd–Warshall algorithm. I will be adding exercises soon. Good luck!
2. An exercise with solution description: SPOJ RDNWK
3. A problem to try yourself: Codeforces