Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Floyd Warshall Algorithm is one of the famous graph algorithm for finding shortest path between a node to every other node. In this article at OpenGenus, we have implemented Floyd Warshall Algorithm in C++ programming language.
Table of contents:
- what is shortest path?
- Algorithm
- Pseudocode
- Step by step C++ Implementation of Floyd-Warshall algorithm
- Complete Implementation in C++
- Time and space complexities
- Applications
WHAT IS SHORTEST PATH?
Any path that takes least amount of edge weight is called as shortest path in a weighted graph.
Algorithm
Floyd-Warshall algorithm is used to find the shortest distance between all available pair of nodes.It is named after scientits Robert W. Floyd and Stephen Warshall.
The main thought process in this algorithm is to Travel through every node and find shortest path.It is also called as multi source shortest path algorithm.The graph should not contain negative cycles for finding the shortest paths between pairs of vertices.
STEPS BY STEP EXPLANATION:
INITIAL STEPS:
Initially we create a adjacency matrix that is used to store shortest path between every pair(i,j) of vertices.
We will set the values of adjacency matrix as follows:
- If i and j represent same vertex then adj[i][j]=0.
- If there is a edge between i and j then adj[i][j] is
equal to weight of that edge. - If not both of the above cases set adj[i][j] to infinity
MAIN FUNCTION:
Update the adjacency matrix for all pairs(i,j), for each intermediate vertex k starting from 1 to total number of vertices.
adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j]
The algorithm's main idea is that it iterates over all vertices and considers each vertex as a potential intermediate vertex for the shortest path between any pair of vertices and finds the shortest distace by considering all possible intermediate vertices.
After completing the main function,the adj matrix will have shortest path between every pair of vertices.
PSEUDOCODE
Floyd-Warshal()
d[v][u] = infinity for each pair (v,u)
d[v][v] = 0 for each vertex v
for k = 1 to n
for i = 1 to n
for j = 1 to n
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
Step by step C++ Implementation of Floyd-Warshall algorithm
- Graph Representation using Vector of Vectors:
#include <iostream>
#include <vector>
const int INF = 1e9; // A large value representing infinity
int main() {
int n = 4; // Number of vertices
// Initialize the graph using a vector of vectors
std::vector<std::vector<int>> graph = {
{0, 3, 6, INF},
{INF, 0, 2, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
// Rest of the implementation will follow...
return 0;
}
Explanation:
In C++, we can represent the weighted graph using a vector of vectors. The element graph[i][j] will represent the weight of the edge from vertex i to vertex j. We use a special value (INF) to represent the absence of an edge between two vertices.
Using a vector of vectors allows us to represent an arbitrary-sized graph with ease. It also provides dynamic memory allocation, meaning the size of the graph does not need to be known at compile time.
- Initialize Distance Matrix using Vectors:
To store the shortest distances between all pairs of vertices, we will use another 2D vector distance. We initialize it with the same dimensions as the graph and set all elements to a large value (INF). We also set the diagonal elements to 0, as the shortest distance from a vertex to itself is 0.
std::vector<std::vector<int>> floyd_warshall(const std::vector<std::vector<int>>& graph) {
int n = graph.size();
std::vector<std::vector<int>> distance(n, std::vector<int>(n, INF));
// Initialize the distance matrix
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) {
distance[i][j] = 0;
} else if (graph[i][j] != 0) {
distance[i][j] = graph[i][j];
}
}
}
// Rest of the implementation will follow...
return distance;
}
Using vectors to represent the distance matrix allows us to resize it dynamically based on the size of the graph.
- Main Loop - Finding Shortest Paths:
The main loop is the core part of the Floyd-Warshall algorithm. It iterates through all vertices as potential intermediate vertices and updates the shortest distance between all pairs of vertices.
std::vector<std::vector<int>> floyd_warshall(const std::vector<std::vector<int>>& graph) {
// ... (previous code)
// Main loop
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// Update the distance using vertex k as an intermediate point
if (distance[i][k] != INF && distance[k][j] != INF) {
distance[i][j] = std::min(distance[i][j], distance[i][k] + distance[k][j]);
}
}
}
}
// ... (remaining code)
return distance;
}
In this loop, k represents the intermediate vertex being considered, and i and j represent the source and destination vertices, respectively. We check if the distance between vertices i and k and between k and j is not INF. If so, we consider the path from i to j through k as a potential shortest path and update the distance matrix accordingly.
- Printing the Results:
Finally, we can print the results of the shortest distances between all pairs of vertices.
int main() {
// ... (previous code)
// Call the Floyd-Warshall algorithm function
std::vector<std::vector<int>> shortest_distances = floyd_warshall(graph);
// Display the shortest distances between all pairs of vertices
std::cout << "Shortest distances between all pairs of vertices:\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (shortest_distances[i][j] == INF) {
std::cout << "INF ";
} else {
std::cout << shortest_distances[i][j] << " ";
}
}
std::cout << std::endl;
}
// ... (remaining code)
return 0;
}
Here, we check if the value of shortest_distances[i][j] is INF to print "INF" if there is no path between vertices i and j. Otherwise, we print the actual shortest distance.
By breaking down the implementation into small code snippets, it becomes easier to understand the individual components of the Floyd-Warshall algorithm in C++. The vector-based representation allows dynamic resizing and simplifies handling different graph sizes, making it a flexible and convenient choice for this algorithm.
Complete Implementation in C++
#include <iostream>
#include <vector>
const int INF = 1e9; // A large value representing infinity
std::vector<std::vector<int>> floyd_warshall(const std::vector<std::vector<int>>& graph) {
int n = graph.size();
std::vector<std::vector<int>> distance(n, std::vector<int>(n, INF));
// Initialize the distance matrix
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) {
distance[i][j] = 0;
} else if (graph[i][j] != 0) {
distance[i][j] = graph[i][j];
}
}
}
// Main loop
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// Update the distance using vertex k as an intermediate point
if (distance[i][k] != INF && distance[k][j] != INF) {
distance[i][j] = std::min(distance[i][j], distance[i][k] + distance[k][j]);
}
}
}
}
return distance;
}
int main() {
int n = 4; // Number of vertices
std::vector<std::vector<int>> graph = {
{0, 3, 6, 0},
{0, 0, 2, 0},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
// Call the Floyd-Warshall algorithm function
std::vector<std::vector<int>> shortest_distances = floyd_warshall(graph);
// Display the shortest distances between all pairs of vertices
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (shortest_distances[i][j] == INF) {
std::cout << "No path from vertex " << i << " to " << j << "\n";
} else {
std::cout << "Shortest distance from vertex " << i << " to " << j << " is: " << shortest_distances[i][j] << "\n";
}
}
}
return 0;
}
GIVEN GRAPH FOR ABOVE EXMAPLE:
Edge: (0, 1) Weight: 3
Edge: (0, 2) Weight: 6
Edge: (1, 2) Weight: 2
Edge: (2, 3) Weight: 1
OUTPUT:
Shortest distances between all pairs of vertices:
0 3 5 6
INF 0 2 3
INF INF 0 1
INF INF INF 0
TIME COMPLEXITIES:
Worst case time complexity: Θ(V^3)
Best case time complexity: Θ(V^3)
Space complexity: Θ(V^2)
where v is the number of vertices.
REAL LIFE APPLICATIONS:
Floyd-Warshall algorithm is a versatile algorithm used in various applications that involve finding shortest paths in weighted graphs.Here are some real life examples where we can use this:
- Routing and Networking Areas
- Transportation and Traffic Management
- Robotics and Autonomous Vehicles
- Flight Scheduling and Air Traffic Control
- Social Network Analysis
