Why the Floyd-Warshall Algorithm Works: Correctness Proof
The Floyd-Warshall algorithm is based on the principle of optimal substructure, which states that if the shortest path from node i to j passes through an intermediate node k, then the subpaths i → k and k → j must also be shortest paths. This recursive structure allows the algorithm to build the solution incrementally.
The algorithm follows an iterative dynamic programming approach. For each node k, it updates the shortest path between every pair (i, j) by checking if the path i → k → j is shorter than the current i → j path. Since it only uses vertices numbered up to k at each step, all required subpaths have already been computed by the time k is considered.
By iterating through all vertices as potential intermediates, the algorithm exhaustively evaluates all possible paths and ensures the shortest one is chosen. Thus, it correctly computes the shortest paths between all pairs of nodes in a graph, even in the presence of negative edge weights (but no negative cycles).
Benefits
You might think as to what are the benefits of using the Floyd Warshall Algorithm for solving such problems. The benefits are that the algorithm does not require unnecessary steps and processes, is easy to be executed and has the minimum time complexity in the worst case. It has O(n^2) time complexity while other algorithms have O(n^3) time complexity.
Applications
The Floyd Warshall Algorithm has a number of applications in real life too. It is not only used in mathematical operations like these but is also very useful in daily life problems of networking. Its other applications are:
- All-pairs shortest path: Computing shortest paths between every pair of vertices in a directed graph.
- Transitive closure: Basically for determining reachability of nodes. Transitive closure has many uses in determining relationships between things.
// Transitive closure variant of Floyd-Warshall
// input: d is an adjacency matrix for n nodes.
// reachability of a node to itself e.g. d[i][i] should be initialized to 1.
// output: d[i][j]=1 will mean j can be reached from i.
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i][k]==’1′ && d[k][j]==’1′) d[i][j]=’1′;
- Detecting negative-weight cycles in graphs. (If there is a negative weight cycle, the distance from the start node to itself will be negative after running the algorithm).
- Bipartiteness – (Although you can also do Bipartiteness checking based on single-source shortest paths algorithms like Dijkstra). Basically, you can detect whether a graph is bipartite via parity. Set all edges to a weight of 1, all vertices at an odd shortest-distance away from some arbitrary root V are in one subset, all vertices at an even distance away are in another subset.
- Minimax: This in graph problems involves finding a path between two nodes that minimises the maximum cost along the path. (Example problems include finding feasible paths to take by car with a limited fuel tank and rest stations at every node). See below for the tweak for Floyd-Warshall that enables finding minimax. You can also add in an update to a predecessor matrix in order to keep track of the actual path found.
// Minimax variant of Floyd-Warshall example
// input: d is a distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
// the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the minimax path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
- Maximin: The other way around from Minimax – here you have problems where you need to find the path that maximises the minimum cost along a path. (Example problems include trying to maximise the load a cargo truck can take when roads along a path may have a weight limit, or trying to find a network routing path that meets a minimum bandwidth requirement for some application). See below for the tweak for Floyd-Warshall that enables finding maximin.
// Maximin variant of Floyd-Warshall example
// input: d is a distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
// the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the maximin path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
- Safest path: Similar in construction of Floyd-Warshall to minimax and maximin – Need to maximise the product of probabilities of survival along a path. Simply change the max to a min to find the most dangerous path.
// Safest path variant of Floyd-Warshall example
// input: p is a probability matrix (probability of survival) for n nodes
// e.g. p[i][j] is the probability of survival moving directly from i to j.
// the probability from a node to itself e.g. p[i][i] should be initialized to 1
// output: p[i][j] will contain the probability of survival using the safest path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
p[i][j] = max(p[i][j], p[i][k] * p[k][j]);
Given the popularity and importance of this algorithm, learning and solving this one is a must-have.
Check out this problem - Frog Jump
Advantages of Floyd-Warshall Algorithm
- Solves Multiple Problems:
Floyd-Warshall is highly versatile—it can compute all-pairs shortest paths, detect negative weight cycles, and find the transitive closure of a graph. This makes it a powerful tool for many graph-related problems. - Simplicity & Easy Implementation:
The algorithm is straightforward and uses only three nested loops, which makes it easy to understand and implement, especially for beginners learning graph algorithms or dynamic programming. - Handles Negative Weights:
Unlike Dijkstra’s algorithm, Floyd-Warshall works well with negative edge weights (as long as there are no negative cycles), making it more broadly applicable. - Deterministic and Systematic:
The approach ensures that all pairs are covered systematically, leaving no edge case unchecked, leading to consistent and predictable results. - Parallelizable:
Due to its regular structure and lack of dependencies between some iterations, the algorithm can be parallelized, allowing faster performance on multi-core processors or GPUs. - Time Complexity (O(n³)):
Although cubic in nature, for dense graphs or when all-pairs shortest paths are needed, the O(n³) time complexity is acceptable and often competitive.
Disadvantages of Floyd-Warshall Algorithm
- High Theoretical Complexity:
While implementation is simple, understanding the theoretical basis (like dynamic programming and optimal substructure) can be challenging for beginners. - Inefficient for Sparse Graphs:
In large graphs with relatively few edges, algorithms like Dijkstra’s (for single-source) or Johnson’s (for all-pairs) may be more efficient than Floyd-Warshall’s O(n³) approach. - Memory Usage:
The algorithm requires O(n²) space to store distances, which can be problematic for graphs with thousands of nodes. - Slower on Very Large Graphs:
Despite being systematic, it’s not scalable for very large graphs due to its time complexity. This can lead to performance bottlenecks in real-time systems or big data applications. - Can Misbehave with Negative Cycles:
If a negative weight cycle exists, Floyd-Warshall will detect it, but shortest path results involving those cycles will be invalid or undefined. This limits its reliability in such cases.
Frequently Asked Questions
What is the Floyd-Warshall algorithm used for?
The Floyd-Warshall algorithm is used to find the shortest path between all pairs of vertices in a graph. This can be useful in a variety of applications, such as in network routing, where it can be used to find the most efficient way to send data between different points in a network.
How does the Floyd-Warshall algorithm work?
The Floyd-Warshall algorithm works by computing the shortest path between all pairs of vertices in a graph. It does this by maintaining a table of the shortest distances between pairs of vertices, and then updating that table using dynamic programming.
What is the time complexity of the Floyd-Warshall algorithm?
The time complexity of the Floyd-Warshall algorithm is O(n^3), where n is the number of vertices in the graph. This makes it less efficient than other algorithms for finding the shortest path between pairs of vertices, such as Dijkstra's algorithm, which has a time complexity of O((E+V)logV).
What are the advantages of using the Floyd-Warshall algorithm?
The main advantage of using the Floyd-Warshall algorithm is that it is able to find the shortest path between all pairs of vertices in a graph, whereas other algorithms are only able to find the shortest path between a single pair of vertices. This makes it useful in applications where you need to find the shortest path between all pairs of vertices, such as in network routing.
Conclusion
In this blog, we have discussed the Floyd Warshall Algorithm at a glance along with code and benefits. You can also refer
34+ registered 
