#include <iostream>
using namespace std;
#define V 4
#define INF 99999
void printSolution(int dist[][V]);
void floydWarshall (int graph[][V])
{
int dist[V][V], i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < V; k++)
{
for (i = 0; i < V; i++)
{
for (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] == INF)
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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCiNkZWZpbmUgViA0ICAKI2RlZmluZSBJTkYgOTk5OTkgIAogCnZvaWQgcHJpbnRTb2x1dGlvbihpbnQgZGlzdFtdW1ZdKTsgIAogCnZvaWQgZmxveWRXYXJzaGFsbCAoaW50IGdyYXBoW11bVl0pICAKeyAgCiAgICBpbnQgZGlzdFtWXVtWXSwgaSwgaiwgazsgIAogCiAgICBmb3IgKGkgPSAwOyBpIDwgVjsgaSsrKSAgCiAgICAgICAgZm9yIChqID0gMDsgaiA8IFY7IGorKykgIAogICAgICAgICAgICBkaXN0W2ldW2pdID0gZ3JhcGhbaV1bal07ICAKIAogICAgZm9yIChrID0gMDsgayA8IFY7IGsrKykgIAogICAgeyAgCiAgICAgICAgZm9yIChpID0gMDsgaSA8IFY7IGkrKykgIAogICAgICAgIHsgIAogICAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgVjsgaisrKSAgCiAgICAgICAgICAgIHsgICAKICAgICAgICAgICAgICAgIGlmIChkaXN0W2ldW2tdICsgZGlzdFtrXVtqXSA8IGRpc3RbaV1bal0pICAKICAgICAgICAgICAgICAgICAgICBkaXN0W2ldW2pdID0gZGlzdFtpXVtrXSArIGRpc3Rba11bal07ICAKICAgICAgICAgICAgfSAgCiAgICAgICAgfSAgCiAgICB9ICAKIAogICAgcHJpbnRTb2x1dGlvbihkaXN0KTsgIAp9ICAKIAp2b2lkIHByaW50U29sdXRpb24oaW50IGRpc3RbXVtWXSkgIAp7ICAKICAgIGNvdXQ8PCJUaGUgZm9sbG93aW5nIG1hdHJpeCBzaG93cyB0aGUgc2hvcnRlc3QgZGlzdGFuY2VzIgogICAgICAgICAgICAiIGJldHdlZW4gZXZlcnkgcGFpciBvZiB2ZXJ0aWNlcyBcbiI7ICAKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgVjsgaSsrKSAgCiAgICB7ICAKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IFY7IGorKykgIAogICAgICAgIHsgIAogICAgICAgICAgICBpZiAoZGlzdFtpXVtqXSA9PSBJTkYpICAKICAgICAgICAgICAgICAgIGNvdXQ8PCJJTkYiPDwiICAgICAiOyAgCiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIGNvdXQ8PGRpc3RbaV1bal08PCIgICAgICI7ICAKICAgICAgICB9ICAKICAgICAgICBjb3V0PDxlbmRsOyAgCiAgICB9ICAKfSAgCiAKaW50IG1haW4oKSAgCnsgIAogICAgaW50IGdyYXBoW1ZdW1ZdID0geyB7MCwgNSwgSU5GLCAxMH0sICAKICAgICAgICAgICAgICAgICAgICAgICAge0lORiwgMCwgMywgSU5GfSwgIAogICAgICAgICAgICAgICAgICAgICAgICB7SU5GLCBJTkYsIDAsIDF9LCAgCiAgICAgICAgICAgICAgICAgICAgICAgIHtJTkYsIElORiwgSU5GLCAwfSAgCiAgICAgICAgICAgICAgICAgICAgfTsgIAogCiAgICBmbG95ZFdhcnNoYWxsKGdyYXBoKTsgIAogICAgcmV0dXJuIDA7ICAKfQ==