#include <bits/stdc++.h>
using namespace std;
// Number of vertices in the adjMatrix
#define N 4
// Function to print the transitive closure of graph
void printTransitiveClosure(int cost[N][N])
{
for (int v = 0; v < N; v++)
{
for (int u = 0; u < N; u++)
{
if (cost[v][u] == INT_MAX)
cout << setw(3) << "0";
else
cout << setw(3) << "1";
}
cout << endl;
}
}
// The function runs Floyd-Warshell algorithm and
// returns transitive closure of the graph
void FloydWarshell(int adjMatrix[][N])
{
// cost[] stores shortest-path information
int cost[N][N];
// initialize cost[]
for (int v = 0; v < N; v++)
{
for (int u = 0; u < N; u++)
{
// initally cost would be same as weight
// of the edge
cost[v][u] = adjMatrix[v][u];
}
}
// Run Floyd-Warshell
for (int k = 0; k < N; k++)
{
for (int v = 0; v < N; v++)
{
for (int u = 0; u < N; u++)
{
// If vertex k is on the shortest path from v to u,
// then update the value of cost[v][u]
if (cost[v][k] != INT_MAX && cost[k][u] != INT_MAX
&& cost[v][k] + cost[k][u] < cost[v][u])
cost[v][u] = cost[v][k] + cost[k][u];
}
}
}
// Print the transitive closure of graph
printTransitiveClosure(cost);
}
int main()
{
// given adjacency representation of matrix
int adjMatrix[N][N] =
{
{ 0, INT_MAX, -2, INT_MAX },
{ 4, 0, INT_MAX, INT_MAX },
{ INT_MAX, INT_MAX, 0, INT_MAX },
{ INT_MAX, -1, INT_MAX, 0 }
};
// Run Floyd Warshell algorithm
FloydWarshell(adjMatrix);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBOdW1iZXIgb2YgdmVydGljZXMgaW4gdGhlIGFkak1hdHJpeAojZGVmaW5lIE4gNAoKLy8gRnVuY3Rpb24gdG8gcHJpbnQgdGhlIHRyYW5zaXRpdmUgY2xvc3VyZSBvZiBncmFwaAp2b2lkIHByaW50VHJhbnNpdGl2ZUNsb3N1cmUoaW50IGNvc3RbTl1bTl0pCnsKCWZvciAoaW50IHYgPSAwOyB2IDwgTjsgdisrKQoJewoJCWZvciAoaW50IHUgPSAwOyB1IDwgTjsgdSsrKQoJCXsKCQkJaWYgKGNvc3Rbdl1bdV0gPT0gSU5UX01BWCkKCQkJCWNvdXQgPDwgc2V0dygzKSA8PCAiMCI7CgkJCWVsc2UKCQkJCWNvdXQgPDwgc2V0dygzKSA8PCAiMSI7CgkJfQoJCWNvdXQgPDwgZW5kbDsKCX0KfQoKLy8gVGhlIGZ1bmN0aW9uIHJ1bnMgRmxveWQtV2Fyc2hlbGwgYWxnb3JpdGhtIGFuZCAKLy8gcmV0dXJucyB0cmFuc2l0aXZlIGNsb3N1cmUgb2YgdGhlIGdyYXBoCnZvaWQgRmxveWRXYXJzaGVsbChpbnQgYWRqTWF0cml4W11bTl0pCnsKCS8vIGNvc3RbXSBzdG9yZXMgc2hvcnRlc3QtcGF0aCBpbmZvcm1hdGlvbgoJaW50IGNvc3RbTl1bTl07CgoJLy8gaW5pdGlhbGl6ZSBjb3N0W10KCWZvciAoaW50IHYgPSAwOyB2IDwgTjsgdisrKSAKCXsKCQlmb3IgKGludCB1ID0gMDsgdSA8IE47IHUrKykgCgkJewoJCQkvLyBpbml0YWxseSBjb3N0IHdvdWxkIGJlIHNhbWUgYXMgd2VpZ2h0IAoJCQkvLyBvZiB0aGUgZWRnZQoJCQljb3N0W3ZdW3VdID0gYWRqTWF0cml4W3ZdW3VdOwoJCX0KCX0KCQoJLy8gUnVuIEZsb3lkLVdhcnNoZWxsCglmb3IgKGludCBrID0gMDsgayA8IE47IGsrKykgCgl7CgkJZm9yIChpbnQgdiA9IDA7IHYgPCBOOyB2KyspIAoJCXsKCQkJZm9yIChpbnQgdSA9IDA7IHUgPCBOOyB1KyspIAoJCQl7CgkJCQkvLyBJZiB2ZXJ0ZXggayBpcyBvbiB0aGUgc2hvcnRlc3QgcGF0aCBmcm9tIHYgdG8gdSwKCQkJCS8vIHRoZW4gdXBkYXRlIHRoZSB2YWx1ZSBvZiBjb3N0W3ZdW3VdCgkJCQlpZiAoY29zdFt2XVtrXSAhPSBJTlRfTUFYICYmIGNvc3Rba11bdV0gIT0gSU5UX01BWAoJCQkJCSYmIGNvc3Rbdl1ba10gKyBjb3N0W2tdW3VdIDwgY29zdFt2XVt1XSkgCgkJCQljb3N0W3ZdW3VdID0gY29zdFt2XVtrXSArIGNvc3Rba11bdV07CgkJCX0KCQl9Cgl9CgoJLy8gUHJpbnQgdGhlIHRyYW5zaXRpdmUgY2xvc3VyZSBvZiBncmFwaAoJcHJpbnRUcmFuc2l0aXZlQ2xvc3VyZShjb3N0KTsKfQoKaW50IG1haW4oKQp7CgkvLyBnaXZlbiBhZGphY2VuY3kgcmVwcmVzZW50YXRpb24gb2YgbWF0cml4CglpbnQgYWRqTWF0cml4W05dW05dID0KCXsgCgkJeyAJCTAsIElOVF9NQVgsICAgICAgLTIsIElOVF9NQVggfSwKCQl7IAkJNCwgCQkwLCAgSU5UX01BWCwgSU5UX01BWCB9LAoJCXsgSU5UX01BWCwgSU5UX01BWCwgCSAgMCwgSU5UX01BWCB9LAoJCXsgSU5UX01BWCwgCQktMSwgSU5UX01BWCwgCSAgIDAgfSAKCX07CgoJLy8gUnVuIEZsb3lkIFdhcnNoZWxsIGFsZ29yaXRobQoJRmxveWRXYXJzaGVsbChhZGpNYXRyaXgpOwoKCXJldHVybiAwOwp9