#include <iostream>
using namespace std;


#define INF 9999
#define V 4

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];
            }
        }
    }
}




int main()
{
    int graph[V][V] = { {0, 4, INF, 9},
                        {INF, 0, 2, INF},
                        {INF, INF, 0, 1},
                        {INF, INF, INF, 0}
                    };
    int dist[V][V];
    floydWarshall(graph);
    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;
    }
    return 0;
}