Algorithm
The Floyd-Warshall algorithm is a graph algorithm that is used to find 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 it can handle graphs with negative weight edges, but it cannot handle graphs with negative weight cycles.
The main idea behind the Floyd-Warshall algorithm is to iteratively update the shortest path estimates between all pairs of vertices by considering all possible intermediate vertices. The algorithm uses a matrix to store the shortest path distances between every pair of vertices. The steps of the algorithm can be summarized as follows:
-
Initialize a matrix
distsuch thatdist[i][j]represents the shortest distance from vertexito vertexj. -
Set the diagonal elements of the matrix to 0, as the shortest distance from a vertex to itself is always 0.
-
For each edge
(u, v)in the graph, setdist[u][v]to the weight of the edge. -
For each vertex
k, iterate over all pairs of vertices(i, j)and updatedist[i][j]to the minimum of its current value and the sum of the distances fromitokand fromktoj.
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 not the most efficient for finding single-source shortest paths or for sparse graphs, but it is simple to implement and is particularly useful when you need to find the shortest paths between all pairs of vertices in a dense graph.
Code Examples
#1 Floyd-Warshall implement in Python
Code -
Python Programming
INF = float('inf')
def floyd_warshall(graph):
num_vertices = len(graph)
dist = [[INF] * num_vertices for _ in range(num_vertices)]
# Initialize the distance matrix with the graph's edge weights
for i in range(num_vertices):
for j in range(num_vertices):
if i == j:
dist[i][j] = 0
elif (i, j) in graph:
dist[i][j] = graph[(i, j)]
# Floyd-Warshall algorithm
for k in range(num_vertices):
for i in range(num_vertices):
for j in range(num_vertices):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# Example usage:
graph = {
(0, 1): 3,
(0, 2): 6,
(1, 2): 1,
(1, 3): 4,
(2, 3): 2,
(3, 0): 7
}
result = floyd_warshall(graph)
# Print the result
for row in result:
print(row)
#2 Floyd-Warshall implement in Java
Code -
Java Programming
public class FloydWarshall {
public static void main(String[] args) {
int[][] graph = {
{0, 5, Integer.MAX_VALUE, 10},
{Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE},
{Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 1},
{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
};
int[][] shortestPaths = floydWarshall(graph);
// Print the result
System.out.println("Shortest paths between all pairs of vertices:");
printSolution(shortestPaths);
}
private static int[][] floydWarshall(int[][] graph) {
int V = graph.length;
int[][] dist = new int[V][V];
// Initialize the distance matrix with the input graph
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// Apply Floyd-Warshall algorithm
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// If vertex k is on the shortest path from i to j, update the distance
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
private static void printSolution(int[][] dist) {
int V = dist.length;
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (dist[i][j] == Integer.MAX_VALUE) {
System.out.print("INF ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}
}
#3 Floyd-Warshall implement in C
Code -
C Programming
#include <stdio.h>
#include <limits.h>
#define V 4 // Number of vertices in the graph
void printSolution(int dist[][V]);
void floydWarshall(int graph[][V]) {
int dist[V][V];
// Initialize the solution matrix with the same values as the input graph
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
// Update dist[][] to include all vertices as intermediate vertices
for (int k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (int i = 0; i < V; i++) {
// Pick all vertices as destination for the above picked source
for (int j = 0; j < V; j++) {
// If vertex k is on the shortest path from i to j,
// then update the value of dist[i][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 shortest distance matrix
printSolution(dist);
}
void printSolution(int dist[][V]) {
printf ("Following matrix shows the 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("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf("\n");
}
}
int main() {
int graph[V][V] = {
{0, 5, INT_MAX, 10},
{INT_MAX, 0, 3, INT_MAX},
{INT_MAX, INT_MAX, 0, 1},
{INT_MAX, INT_MAX, INT_MAX, 0}
};
floydWarshall(graph);
return 0;
}
#4 Floyd-Warshall implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Function to perform Floyd-Warshall algorithm
void floydWarshall(vector < vector<int>>& graph, int V) {
// Initialize the distance matrix with the graph
vector < vector<int>> dist(graph);
// Update the distance matrix by considering all vertices as intermediate vertices
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// If vertex k is on the shortest path from i to j, then update the value of dist[i][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 shortest distances between every pair of vertices
cout << "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) {
cout << "INF\t";
} else {
cout << dist[i][j] << "\t";
}
}
cout << "\n";
}
}
int main() {
// Number of vertices in the graph
int V;
cout << "Enter the number of vertices in the graph: ";
cin >> V;
// Adjacency matrix representation of the graph
vector < vector<int>> graph(V, vector<int>(V, INT_MAX));
// Input the graph
cout << "Enter the adjacency matrix (enter INF for infinity):\n";
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
cin >> graph[i][j];
}
}
// Perform Floyd-Warshall algorithm
floydWarshall(graph, V);
return 0;
}
Demonstration
Floyd-Warshall Data Structure and Algorithm