The Floyd-Warshall algorithm is a dynamic programming algorithm used for finding the shortest paths between all pairs of vertices in a weighted graph. It was proposed by Robert Floyd in 1962 and independently by Stephen Warshall in 1962.
The algorithm works for both directed and undirected graphs and can handle graphs with negative weight edges (as long as there are no negative weight cycles). The main idea behind the Floyd-Warshall algorithm is to iteratively update the shortest path distances between all pairs of vertices by considering all possible intermediate vertices.
Here are the basic steps of the Floyd-Warshall algorithm:
1. **Initialization:**
- Set the distance matrix `D` such that `D[i][j]` is the weight of the edge between vertex `i` and vertex `j` if there is an edge, and infinity if there is no direct edge. Also, set `D[i][i]` to 0 for all vertices `i`.
2. **Iterative Update:**
- For each intermediate vertex `k` (vertices 1 to `N`, where `N` is the total number of vertices), update the distance matrix `D` by considering the possibility of using vertex `k` as an intermediate vertex in the path from vertex `i` to vertex `j`.
```plaintext
D[i][j] = min(D[i][j], D[i][k] + D[k][j])
```
This means, if there is a shorter path from `i` to `j` through vertex `k`, update the distance matrix accordingly.
3. **Result:**
- After the iterative updates, the distance matrix `D` will contain the shortest path distances between all pairs of vertices.
The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number of vertices in the graph. The algorithm is relatively simple to implement and is especially useful for dense graphs or graphs with small to moderate numbers of vertices.
Let's walk through a simple example to illustrate the Floyd-Warshall algorithm. Consider the following weighted directed graph:
1 (A) -----> (B) | \ / | | \ / | | X | | / \ | | / \ | (C) -----> (D) 2
The weights on the edges are shown next to the edges. The goal is to find the shortest paths between all pairs of vertices (A, B, C, D).
1. **Initialization:**
- Set up the initial distance matrix `D`:
```
| A B C D
-------------------
A | 0 1 ∞ ∞
B | ∞ 0 ∞ 2
C | ∞ ∞ 0 ∞
D | ∞ ∞ ∞ 0
```
Here, ∞ represents infinity, and the diagonal elements (e.g., D[A][A], D[B][B], etc.) are set to 0.
2. **Iterative Update:**
- For each intermediate vertex `X`, update the distance matrix:
- For `X = A`:
```plaintext
D[A][B] = min(D[A][B], D[A][A] + D[A][B]) = min(1, 0 + 1) = 1
D[A][C] = min(D[A][C], D[A][A] + D[A][C]) = min(∞, 0 + ∞) = ∞
D[A][D] = min(D[A][D], D[A][A] + D[A][D]) = min(∞, 0 + ∞) = ∞
```
- For `X = B`:
```plaintext
D[B][A] = min(D[B][A], D[B][B] + D[B][A]) = min(∞, 0 + ∞) = ∞
D[B][C] = min(D[B][C], D[B][B] + D[B][C]) = min(∞, 0 + ∞) = ∞
D[B][D] = min(D[B][D], D[B][B] + D[B][D]) = min(2, 0 + 2) = 2
```
- For `X = C`:
```plaintext
D[C][A] = min(D[C][A], D[C][C] + D[C][A]) = min(∞, 0 + ∞) = ∞
D[C][B] = min(D[C][B], D[C][C] + D[C][B]) = min(∞, 0 + ∞) = ∞
D[C][D] = min(D[C][D], D[C][C] + D[C][D]) = min(∞, 0 + ∞) = ∞
```
- For `X = D`:
```plaintext
D[D][A] = min(D[D][A], D[D][D] + D[D][A]) = min(∞, 0 + ∞) = ∞
D[D][B] = min(D[D][B], D[D][D] + D[D][B]) = min(∞, 0 + ∞) = ∞
D[D][C] = min(D[D][C], D[D][D] + D[D][C]) = min(∞, 0 + ∞) = ∞
```
3. **Result:**
- After the first iteration, the distance matrix is updated to:
```
| A B C D
-------------------
A | 0 1 ∞ ∞
B | ∞ 0 ∞ 2
C | ∞ ∞ 0 ∞
D | ∞ ∞ ∞ 0
```
The process is repeated for each intermediate vertex until we reach the final result:
```
| A B C D
-------------------
A | 0 1 3 3
B | ∞ 0 2 2
C | ∞ ∞ 0 4
D | ∞ ∞ ∞ 0
```
The final matrix `D` represents the shortest paths between all pairs of vertices. For example, the shortest path from A to C is A -> B -> D -> C with a total weight of 3.
c implementation for this algorithm:
// Function to print the final distance matrix void printSolution(int dist[V][V]) { printf("Shortest distances between every pair of vertices:\n"); for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (dist[i][j] == INT_MAX) printf("INF\t"); else printf("%d\t", dist[i][j]); } printf("\n"); } } // Function to perform the Floyd-Warshall algorithm void floydWarshall(int graph[V][V]) { int dist[V][V]; // Initialize the distance matrix for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i][j] = graph[i][j]; } } // Update the distance matrix by considering all possible intermediate vertices for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } // Print the final result printSolution(dist); } int main() { // Example graph represented by an adjacency matrix int graph[V][V] = { {0, 1, INT_MAX, INT_MAX}, {INT_MAX, 0, INT_MAX, 2}, {INT_MAX, INT_MAX, 0, INT_MAX}, {INT_MAX, INT_MAX, INT_MAX, 0} }; // Perform the Floyd-Warshall algorithm floydWarshall(graph); return 0; }
In this example, V is the number of vertices in the graph, and the graph array represents the weighted adjacency matrix of the directed graph. The INT_MAX constant is used to represent infinity in the context of the Floyd-Warshall algorithm. The printSolution function is used to display the final result, and floydWarshall is the function that performs the actual algorithm.
0 Comments