#include <iostream> 
using namespace std; 

int V=4  
int INF=99999  
  
 
void printSol(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];  
            }  
        }  
    }  

    printSol(dist);  
}  
void printSol(int dist[][V])  
{  
    cout<<"Urmatoarea matrice prezinta distantele dintre oricare doua noduri \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()  
{  
# matricea initiala trebuie introdusa manual
    int graph[V][V] = { {0, 4, INF, 9},  
                        {INF, 0, 2, INF},  
                        {INF, INF, 0, 1},  
                        {INF, INF, INF, 0}  
                    };  

    floydWarshall(graph);  
    return 0;  
}