Floyd-Warshall Algorithm
Introduction
Floyd-Warshall Algorithm is a Dynamic Programming algorithm used to find the shortest paths between every pair of vertices in a weighted graph. Unlike Dijkstra's Algorithm, which computes the shortest path from a single source, Floyd-Warshall computes the shortest paths between all pairs of vertices simultaneously.
The algorithm repeatedly improves the shortest distances by considering every vertex as an intermediate point between every possible pair of vertices. It works correctly even when the graph contains negative edge weights, provided that no negative weight cycle exists.
Why Do We Need Floyd-Warshall Algorithm?
Many practical applications require the shortest distance between every pair of locations rather than from only one source. Floyd-Warshall Algorithm efficiently computes these distances in a single execution.
| Application | Purpose |
|---|---|
| Navigation Systems | Shortest distance between every pair of cities. |
| Computer Networks | Routing between all computers. |
| Airline Reservation Systems | Finding minimum travel distance between airports. |
| Transportation Planning | Shortest route between all stations. |
| Social Networks | Finding minimum connection paths. |
Prerequisites
| Concept | Description |
|---|---|
| Graph | A collection of vertices connected by weighted edges. |
| Weighted Graph | Each edge has an associated weight or cost. |
| Dynamic Programming | Stores solutions of overlapping subproblems. |
| Adjacency Matrix | Represents the graph in matrix form. |
Working Principle
Initially, the adjacency matrix represents the shortest known distances between all pairs of vertices. The algorithm then considers each vertex one by one as an intermediate vertex. If travelling through this intermediate vertex results in a shorter path, the corresponding distance is updated.
After considering all vertices as intermediate vertices, the matrix contains the shortest distances between every pair of vertices.
Example Graph
| From | To | Weight |
|---|---|---|
| A | B | 3 |
| A | C | 8 |
| B | C | 2 |
| C | D | 1 |
| B | D | 5 |
Illustration
Why is Floyd-Warshall a Dynamic Programming Algorithm?
The shortest path between two vertices may depend upon the shortest paths between smaller pairs of vertices. The algorithm stores these intermediate shortest distances inside the distance matrix and reuses them repeatedly, making it a classic Dynamic Programming algorithm.
Floyd-Warshall Algorithm
FloydWarshall(Graph)
Step 1 : Create the Distance Matrix.
Step 2 : Copy all edge weights into the matrix.
Step 3 : Set Distance(i,i) = 0 for every vertex.
Step 4 : Select every vertex one by one as an intermediate vertex.
Step 5 : Update every pair of vertices using
Distance(i,j) =
min(Distance(i,j),
Distance(i,k)+Distance(k,j))
Step 6 : Repeat until every vertex has been used as an intermediate vertex.
Step 7 : The final matrix contains the shortest distance between every pair of vertices.
Distance Matrix Update
Initially, the matrix stores the direct distances between vertices. During every iteration, the algorithm checks whether using an intermediate vertex reduces the existing distance.
| Iteration | Intermediate Vertex | Result |
|---|---|---|
| 1 | A | Update paths through A. |
| 2 | B | Update paths through B. |
| 3 | C | Update paths through C. |
| 4 | D | Final shortest distances obtained. |
Complexity Analysis
| Parameter | Complexity | Explanation |
|---|---|---|
| Time Complexity | O(VĀ³) | Three nested loops iterate over all vertices. |
| Space Complexity | O(VĀ²) | The algorithm stores the distance matrix. |
Advantages of Floyd-Warshall Algorithm
- Finds the shortest path between every pair of vertices.
- Supports negative edge weights.
- Simple Dynamic Programming solution.
- Easy matrix-based implementation.
- Suitable for dense graphs.
Limitations of Floyd-Warshall Algorithm
- Cannot produce correct shortest paths if a negative weight cycle exists.
- Time complexity O(VĀ³) is high for very large graphs.
- Requires O(VĀ²) memory.
- Not suitable for sparse graphs with thousands of vertices.
Applications of Floyd-Warshall Algorithm
| Application | Description |
|---|---|
| GPS Navigation | Finding shortest routes between all cities. |
| Computer Networks | Network routing analysis. |
| Transportation Systems | Planning railway and road networks. |
| Airline Reservation | Computing minimum travel distances. |
| Social Networks | Finding minimum connection paths. |
| Network Optimization | Determining shortest communication paths. |
Floyd-Warshall Algorithm vs Dijkstra's Algorithm
| Floyd-Warshall Algorithm | Dijkstra's Algorithm |
|---|---|
| Finds shortest paths between all pairs of vertices. | Finds shortest paths from one source vertex. |
| Uses Dynamic Programming. | Uses Greedy Method. |
| Supports negative edge weights. | Does not support negative edge weights. |
| Time Complexity : O(VĀ³) | Time Complexity : O((V+E) log V) |
| Works using a Distance Matrix. | Works using Priority Queue. |
Summary
Floyd-Warshall Algorithm is a Dynamic Programming algorithm used to determine the shortest paths between every pair of vertices in a weighted graph. By repeatedly considering each vertex as an intermediate point, it updates the distance matrix until the shortest distances are obtained. Due to its ability to solve the All-Pairs Shortest Path problem efficiently, it is widely used in transportation systems, communication networks, navigation systems and optimization applications.