FloydWarshall.cpp

#include <bits/stdc++.h>

using namespace std;

// Function to display the matrix
void showMatrix(const vector<vector<long>> &matrix, int numVertices)
{
    for (int i = 0; i < numVertices; i++)
    {
        for (int j = 0; j < numVertices; j++)
        {
            if (matrix[i][j] < 10) // For better alignment
                cout << " ";
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// Floyd-Warshall algorithm
void floydWarshall(vector<vector<long>> &matrix, int n)
{
    for (int k = 0; k < n; k++) // Intermediary vertex
    {
        for (int i = 0; i < n; i++) // Origin vertex
        {
            for (int j = 0; j < n; j++) // Destination vertex
            {
                if (matrix[i][k] != LONG_MAX &&                 // i -> k exists
                    matrix[k][j] != LONG_MAX &&                 // k -> j exists
                    matrix[i][j] > matrix[i][k] + matrix[k][j]) // i -> j is shorter via k
                {
                    matrix[i][j] = matrix[i][k] + matrix[k][j]; // Update i -> j
                }
            }
        }
    }
}

int main()
{
    int numVertices = 5;

    // Initialize matrix with given values
    vector<vector<long>> matrix = {
        {0, 2, 10, 5, 7},
        {2, 0, 3, 3, 1},
        {10, 3, 0, 1, 2},
        {5, 3, 1, 0, LONG_MAX},
        {7, 1, 2, 2, 0}};

    // Display the original matrix
    cout << "Original matrix:" << endl;
    showMatrix(matrix, numVertices);

    // Apply Floyd-Warshall algorithm
    floydWarshall(matrix, numVertices);

    // Display the updated matrix
    cout << "Updated matrix:" << endl;
    showMatrix(matrix, numVertices);

    // Show all shortest paths in 3 columns: source, destination, shortest distance
    cout << "Source\tDestination\tShortest Distance" << endl;
    for (int i = 0; i < numVertices; i++)
        for (int j = 0; j < numVertices; j++)
            cout << i << "\t" << j << "\t\t" << matrix[i][j] << endl;

    return 0;
}