Floyd-Warshall Algorithm
1. What is the Floyd-Warshall Algorithm?β
The Floyd-Warshall Algorithm is used to find the shortest paths between all pairs of vertices in a weighted graph. It works for both directed and undirected graphs and can handle graphs with negative weight edges, but not negative weight cycles.
2. Algorithm for Floyd-Warshall Algorithmβ
- Initialize the distance matrix with the weights of the edges between vertices.
- For each pair of vertices , update the distance matrix by considering the possibility of going through a third vertex to get a shorter path from to .
- The final distance matrix will contain the shortest distances between all pairs of vertices.
3. How Does Floyd-Warshall Algorithm Work?β
- Start with a distance matrix representing the weights of the edges between vertices.
- Update the matrix by considering all possible intermediate vertices for each pair of vertices.
- Repeat this process until all pairs of vertices have been considered, and the matrix stabilizes.
4. Problem Descriptionβ
Given a weighted graph, the Floyd-Warshall Algorithm aims to find the shortest paths between all pairs of vertices in the graph.
5. Examplesβ
Example graph:
0 1 2 3
--------------------
0 | 0 3 β 7
1 | 8 0 2 β
2 | 5 β 0 1
3 | 2 β β 0
6. Constraintsβ
- The graph can have negative weight edges, but not negative weight cycles.
7. Implementationβ
- Python
- C++
- Java
- JavaScript
def floyd_warshall(graph):
V = len(graph)
dist = [[float('inf') for _ in range(V)] for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for u in range(V):
for v in range(V):
if graph[u][v] != 0:
dist[u][v] = graph[u][v]
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
vector<vector<int>> floydWarshall(vector<vector<int>>& graph) {
int V = graph.size();
vector<vector<int>> dist(graph);
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] != numeric_limits<int>::max() && dist[k][j] != numeric_limits<int>::max()) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
return dist;
}
import java.util.*;
class FloydWarshall {
public static int[][] floydWarshall(int[][] graph) {
int V = graph.length;
int[][] dist = new int[V][V];
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
dist[i][j] = graph[i][j];
}
}
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] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
return dist;
}
}
function floydWarshall(graph) {
const V = graph.length;
const dist = [...graph];
for (let k = 0; k < V; ++k) {
for (let i = 0; i < V; ++i) {
for (let j = 0; j < V; ++j) {
if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
return dist;
}
8. Complexity Analysisβ
- Time Complexity: , where is the number of vertices.
- Space Complexity: , for storing the distance matrix.
9. Advantages and Disadvantagesβ
Advantages:β
- Finds the shortest paths between all pairs of vertices.
- Can handle graphs with negative weight edges.
Disadvantages:β
- Inefficient for large graphs due to its cubic time complexity.
- Requires additional space to store the distance matrix.