Problem 20,21 : Floyd Warshall Algorithm: All Pair Shortest Path

 

Floyd Warshall Algorithm: All Pair Shortest Path

by Ujjal Roy

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int main()

{

    ll N=100;

    ll inf=100000;

    ll i,j,k,node,edge;

    ll dis[N][N];

    for(i=0;i<N;i++)

    {

        for(j=0;j<N;j++)

        {

              if(i==j)

              {

                  dis[i][j]=0;

              }

              else dis[i][j]=inf;

        }

    }

    cout<<"Enter number of node and edge : ";

    cin>>node>>edge;

    while(edge--)

    {

         ll u,v,w;

         cin>>u>>v>>w;

         dis[u][v]=w;

    }

    for(k=1;k<=node;k++)

    {

        for(i=1;i<=node;i++)

        {

             for(j=1;j<=node;j++)

             {

                  dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

             }

        }

    }

     for(i=1;i<=node;i++)

     {

         for(j=1;j<=node;j++)

         {

             if(dis[i][j]==inf)

             {

                 cout<<"N ";

             }

             else cout<<dis[i][j]<<" ";

         }

         cout<<endl;

     }

    return 0;

}