#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();

int a[20][20],i,j,k,n;

cout<<"\n----- ALL-PAIRS SHORTEST PATH using Dynamic Programming -----\n\n";
cout<<"Enter the No. of Nodes in Graph : ";
cin>>n;

cout<<\n\n---- Enter the Distance b/w Nodes ----";
cout<<"\n\n(Note : Enter Distance=100 if there is No Direct Edge b/w any Two Nodes \n";
cout<<"We are Assuming 100 at the Place of Infinity)\n\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<"Node "<<i<<" to Node "<<j<<" : ";
cin>>a[i][j];
}
cout<<endl;
}

cout<<"\nAdjaceny Matrix is :\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<" "<<a[i][j]<<"   ";
}
cout<<endl;
}


for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{

if(a[i][j]>a[i][k]+a[k][j])
{
a[i][j]=a[i][k]+a[k][j];
}


}
}
}

cout<<"\n\nShortest Path Matrix is :\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<" "<<a[i][j]<<"   ";
}
cout<<endl;
}

getch();
}