floyd warshall Algorithm
The Floyd-Warshall algorithm is a dynamic programming approach to find the shortest path between all pairs of nodes in a weighted graph with positive or negative edge weights, but without negative cycles. Developed by Robert Floyd and Stephen Warshall, it is an efficient method for solving the all-pairs shortest path problem, which is crucial in various applications such as network routing, travel planning, and social network analysis. The algorithm has a time complexity of O(n^3), where n is the number of vertices in the graph, making it a suitable choice for small to moderately-sized graphs.
The core idea behind the Floyd-Warshall algorithm is to iteratively update the distance between each pair of nodes by considering an intermediate node that potentially reduces the path length between them. Initially, the distance matrix is populated with the direct edge weights between nodes or with infinity if there is no direct edge. Then, for each intermediate node, the algorithm checks if the distance between a pair of nodes can be reduced by going through the intermediate node. If so, the distance matrix is updated with the shorter path. After considering all intermediate nodes, the final distance matrix contains the shortest path between all pairs of nodes, which can be easily retrieved for any desired pair.
//
// Floyd Warshall algorithm implementation in C++
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/graphs/
// https://github.com/allalgorithms/cpp
//
// Contributed by: Nikunj Taneja
// Github: @underscoreorcus
//
#include<cstdio>
#define V 4 // Number of vertices in the graph
#define INF 1e7
void printSolution(int dist[][V]);
void floydWarshall (int graph[][V])
{
int dist[V][V], i, j, k;
/* Initialize the solution matrix same as input graph matrix. Or
we can say the initial values of shortest distances are based
on shortest paths considering no intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
/* Add all vertices one by one to the set of intermediate vertices.
---> Before start of an iteration, we have shortest distances between all
pairs of vertices such that the shortest distances consider only the
vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of an iteration, vertex no. k is added to the set of
intermediate vertices and the set becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (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] + 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 ("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)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf("\n");
}
}
int main()
{
// Sample graph
int graph[V][V] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(graph);
return 0;
}
