0% completed
The Floyd-Warshall algorithm is a fundamental algorithm in computer science used for finding shortest paths in a weighted graph with positive or negative edge weights (but no negative cycles). It is particularly useful for dense graphs where we need to compute shortest paths between all pairs of vertices. The algorithm works by progressively improving the estimate of the shortest path between any two vertices by considering all possible paths through intermediate vertices.
- Goal: To find the shortest path between all pairs of vertices in a weighted graph.
- Approach: Dynamic Programming. The algorithm iteratively updates the shortest path estimates by considering paths that pass through intermediate vertices.
The Floyd-Warshall algorithm uses a distance matrix, where the entry at row i
and column j
represents the shortest distance from vertex i
to vertex j
. Initially, this matrix is populated with direct edge weights, and the algorithm systematically updates it to reflect the shortest paths considering all possible intermediate vertices.
Step-by-Step Algorithm
-
Initialize the Distance Matrix:
- Create a matrix to store the shortest distances between all pairs of vertices.
- Initialize the matrix with the input graph’s edge weights. Use a large value (INF) to represent the absence of an edge.
-
Iterate Over All Pairs of Vertices:
- For each pair of vertices (i, j), update the distance between them considering each vertex as an intermediate vertex.
- If the path from i to j through vertex k is shorter than the direct path from i to j, update the distance matrix.
-
Update Distance Matrix:
- For each pair of vertices (i, j), update the distance as: ( \text{distance}[i][j] = \min(\text{distance}[i][j], \text{distance}[i][k] + \text{distance}[k][j]) )
- Repeat this process for all vertices as the intermediate vertex.
-
Print the Final Distance Matrix:
- After processing all vertices, the distance matrix will contain the shortest distances between all pairs of vertices.
Algorithm Walkthrough
Consider the example graph represented by the following adjacency matrix:
Graph:
{
{ 0, 2, INF, 6 },
{ INF, 0, 3, 8 },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 }
}
-
Initialize the Distance Matrix:
Distance Matrix: { { 0, 2, INF, 6 }, { INF, 0, 3, 8 }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } }
-
Iterate Over All Pairs of Vertices:
-
Using Vertex 0 as Intermediate:
Updated Distance Matrix: { { 0, 2, INF, 6 }, { INF, 0, 3, 8 }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } } (No change since there are no shorter paths through vertex 0)
-
Using Vertex 1 as Intermediate:
Updated Distance Matrix: { { 0, 2, 5, 6 }, { INF, 0, 3, 8 }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } } (Distance from 0 to 2 updated from INF to 5 through vertex 1)
-
Using Vertex 2 as Intermediate:
Updated Distance Matrix: { { 0, 2, 5, 6 }, { INF, 0, 3, 4 }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } } (Distance from 1 to 3 updated from 8 to 4 through vertex 2)
-
Using Vertex 3 as Intermediate:
Final Distance Matrix: { { 0, 2, 5, 6 }, { INF, 0, 3, 4 }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } } (No further changes)
-
-
Print the Final Distance Matrix:
- The final distance matrix represents the shortest distances between all pairs of vertices in the graph.
Code
Complexity Analysis
Time Complexity
The Floyd-Warshall algorithm runs in O(V^3) time, where (V) is the number of vertices in the graph. This is because the algorithm consists of three nested loops, each running (V) times.
Space Complexity
The space complexity is O(V^2) because we need to store the distance matrix, which holds the shortest distances between every pair of vertices.
Differences Between Dijkstra's, Bellman-Ford, and Floyd-Warshall Algorithms
Feature | Dijkstra's Algorithm | Bellman-Ford Algorithm | Floyd-Warshall Algorithm |
---|---|---|---|
Purpose | Single-source shortest path for all nodes in a graph | Single-source shortest path for all nodes in a graph | All-pairs shortest path for all nodes in a graph |
Graph Type | Works only with non-negative weights | Handles both positive and negative weights (no negative cycles) | Handles both positive and negative weights (no negative cycles) |
Time Complexity | O(V^2) for matrix representation, O(E + V \log V) with a min-heap | O(VE) | O(V^3) |
Space Complexity | O(V^2) for adjacency matrix, O(E + V) for adjacency list | O(V) for distance array | O(V^2) |
Dynamic Programming | No | Yes | Yes |
Greedy Approach | Yes | No | No |
Negative Weights | No | Yes (handles negative weights) | Yes (handles negative weights) |
Negative Cycles | No | Detects negative cycles | Detects negative cycles |
Use Case | Finding shortest path from a single source to all nodes | Finding shortest path from a single source to all nodes, detecting negative cycles | Finding shortest paths between all pairs of nodes |
Optimal for | Dense graphs (with O(V^2) complexity) or sparse graphs with a priority queue | Graphs with negative weights | Dense graphs |
Initialization | Initializes distances to infinity except the source node | Initializes distances to infinity except the source node | Initializes the distance matrix with edge weights |
Relaxation | Relaxes all edges (V-1) times | Relaxes all edges (V-1) times | Updates shortest paths considering each vertex as an intermediate vertex |
Iteration Over Edges | Uses a priority queue to pick the minimum distance vertex | Iterates over all edges | Iterates over all pairs of nodes |
Cycle Detection | Not applicable | Detects negative weight cycles | Not applicable (can be used to detect negative cycles) |
Algorithm Type | Greedy | Dynamic Programming | Dynamic Programming |
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible