Floyd Warshall
Introduction:
This algorithm gives shortest paths in \(O(|V|^3)\) time from every vertex to every other vertex.
Problem Statement:
print the shortest paths from every vertex to every other vertex.
Algorithm
1. we have an array of n numbers.
2. create |V| X |V| array \(dist[][] = \infty \)
3. for each vertex k in V we relax dist[i][j] for every pair of vertices i, j .
4. Relax \(dist[i][j]\) will set \(dist[i][j] = dist[i][k]+dist[k][j]\)
if \(dist[i][j] > dist[i][k]+dist[k][j]\)
Code :
// shortest path between every pair of vertices
// O(V^3)
#include <bits/stdc++.h>
using namespace std;
#define adjacency_list map<int, vector<pair<int, int>>>
#define mp make_pair
#define INF INT_MAX
typedef struct edge
{
int u;
int v;
int w;
} Edge;
typedef struct graph
{
adjacency_list adj;
int num_edges;
int num_vertices;
Edge *edge;
} graph;
void floyd_warshall(graph G)
{
///// initialisation
int dist[G.num_vertices][G.num_vertices];
for (int i = 0; i < G.num_vertices; i++)
{
for (int j = 0; j < G.num_vertices; j++)
{
dist[i][j] = INF;
}
dist[i][i] = 0;
}
for (int i = 0; i < G.num_edges; i++)
{
dist[G.edge[i].u][G.edge[i].v] = G.edge[i].w;
}
////////// main algorithm
for (int k = 0; k < G.num_vertices; k++)
{
for (int i = 0; i < G.num_vertices; i++)
{
for (int j = 0; j < G.num_vertices; j++)
{
if (dist[k][j] != INF && dist[i][k] != INF && dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
////// printing out
for (int i = 0; i < G.num_vertices; i++)
{
for (int j = 0; j < G.num_vertices; j++)
{
if (dist[i][j] == INF)
{
cout << "INF ";
}
else
{
printf("%-4d ", dist[i][j]);
}
}
cout << "\n";
}
}
int main()
{
// undirected graph
graph G; // u - {{v1,w1}, {v2, w2}, .... {vk,wk}}
cin >> G.num_vertices;
cin >> G.num_edges;
G.edge = new Edge[G.num_edges];
int u, v, w;
for (int i = 0; i < G.num_edges; i++)
{
cin >> G.edge[i].u >> G.edge[i].v >> G.edge[i].w;
}
floyd_warshall(G);
// cout << "\n";
}
Complexity Analysis :
Time complexity : \(O(n^3)\).