#include <iostream>
#include <iomanip>

using namespace std;

const int V = 5;
const int INF = 99999;

void print_solution(int dist[][V]);

void floyd_warshall(int graph[][V])
{
    /*
        this function is designed to run the Floyd-Warshall algorithm on a given graph with an adjacency matrix
    */
    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][j] > (dist[i][k] + dist[k][j])
                    && (dist[k][j] != INF
                        && dist[i][k] != INF))
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
    print_solution(dist);
}

void print_solution(int dist[][V])
{
    /*
        this function will print the paths and their costs between all pairs of vertices
    */
    cout << "Shortes paths between every pair of vertices\n" << endl;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cout << setw(6);
            if (dist[i][j] == INF)
                cout << "INF"
                    << " ";
            else
                cout << dist[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    int graph[V][V] = {
        { 0, 5, INF, 17, INF },
        { INF, 0, 3, INF, INF },
        { -5, INF, 0, 1, INF },
        { INF, INF, 25, 0, 1 },
        { INF, 4, INF, INF, 0 }
    };

    floyd_warshall(graph);
    return 0;
}