Introduction
The Floyd-Warshall algorithm is a fundamental algorithm in computer science, widely used for finding shortest paths in a weighted graph with positive or negative edge weights. This algorithm is particularly important for its ability to handle graphs with negative weight edges, provided there are no negative weight cycles. The essence of the Floyd-Warshall algorithm lies in its dynamic programming approach, which iteratively improves the solution through a series of relaxation steps. It is defined by the formula:
![\[ \text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j]) \]](https://tutcoach.com/wp-content/ql-cache/quicklatex.com-1788fd982f77361e1fff8b9164527434_l3.png "Rendered by QuickLaTeX.com")
where dist[i][j] is the shortest distance from node i to node j, and k is an intermediate node.
Prerequisites
To fully grasp the Floyd-Warshall algorithm and implement it in C++, the following prerequisites are necessary:
- Basic understanding of Graph Theory: Concepts such as vertices, edges, and weight.
- Dynamic Programming: Familiarity with the dynamic programming paradigm.
- C++ Programming: Proficiency in C++ including arrays, loops, and functions.
Floyd-Warshall Algorithm Explained
The Floyd-Warshall algorithm works by iteratively considering each vertex as an intermediate point between every pair of vertices. It starts with the initial weights of the edges and progressively refines the shortest paths by including one intermediate vertex at a time. The key idea is to check if a path through an intermediate vertex is shorter than the direct path.
Example 1: Simple Graph to Implement Floyd-Warshall Algorithm
Code
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
#define V 4
void printSolution(int dist[][V]);
void floydWarshall(int graph[][V]) {
int dist[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] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][V]) {
cout << "The 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)
cout << "INF" << " ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}
int main() {
int graph[V][V] = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(graph);
return 0;
}
Output
The following matrix shows the shortest distances between every pair of vertices:
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
Example 2: Graph with Negative Weights to Implement Floyd-Warshall Algorithm
Code
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
#define V 4
#define INF INT_MAX
void printSolution(int dist[][V]);
void floydWarshall(int graph[][V]) {
int dist[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] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][V]) {
cout << "The 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] == INF)
cout << "INF" << " ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}
int main() {
int graph[V][V] = {
{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}
};
floydWarshall(graph);
return 0;
}
Output
The following matrix shows the shortest distances between every pair of vertices:
0 3 7 5
2 0 6 4
3 1 0 5
5 4 2 0
Example 3: Larger Graph with Mixed Weights to Implement Floyd-Warshall Algorithm
Code
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
#define V 5
#define INF INT_MAX
void printSolution(int dist[][V]);
void floydWarshall(int graph[][V]) {
int dist[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] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][V]) {
cout << "The 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] == INF)
cout << "INF" << " ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}
int main() {
int graph[V][V] = {
{0, 2, INF, 1, 8},
{6, 0, 3, 2, INF},
{INF, INF, 0, 4, INF},
{INF, INF, 2, 0, 3},
{3, INF, INF, 5, 0}
};
floydWarshall(graph);
return 0;
}
Output
The following matrix shows the shortest distances between every pair of vertices:
0 2 5 1 4
5 0 3 2 5
7 9 0 4 7
5 7 2 0 3
3 5 8 4 0
Conclusion
The Floyd-Warshall algorithm is a powerful tool for solving the all-pairs shortest path problem in graphs, especially those with negative weights. Its simplicity and efficiency make it suitable for a wide range of applications, from network routing to geographic information systems