floydwarshall.cpp

#include <iostream>
using namespace std;

class Graph {
    int **dist;
    int vertices;

public:
    Graph(int v) {
        vertices = v;
        dist = new int*[vertices];
        for (int i = 0; i < vertices; i++) {
            dist[i] = new int[vertices];
            for (int j = 0; j < vertices; j++) {
                if (i == j)
                    dist[i][j] = 0;
                else
                    dist[i][j] = 1e9; // Large value representing infinity
            }
        }
    }

    void addEdge(int u, int v, int weight) {
        dist[u][v] = weight;
    }

    void floydWarshall() {
        for (int k = 0; k < vertices; k++) {
            for (int i = 0; i < vertices; i++) {
                for (int j = 0; j < vertices; j++) {
                    if (dist[i][k] != 1e9 && dist[k][j] != 1e9 && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }

    void printDistances() {
        cout << "Shortest distances between every pair of vertices:\n";
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                if (dist[i][j] == 1e9)
                    cout << "INF ";
                else
                    cout << dist[i][j] << " ";
            }
            cout << "\n";
        }
    }

    ~Graph() {
        for (int i = 0; i < vertices; i++) {
            delete[] dist[i];
        }
        delete[] dist;
    }
};

int main() {
    int v, e;
    cout << "Enter number of vertices: ";
    cin >> v;
    Graph g(v);

    cout << "Enter number of edges: ";
    cin >> e;
    cout << "Enter edges (source destination weight):\n";
    for (int i = 0; i < e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.addEdge(u, v, w);
    }

    g.floydWarshall();
    g.printDistances();

    return 0;
}


//This program initializes a graph with user input, runs the Floyd-Warshall algorithm to compute shortest paths between all pairs of vertices, and prints the result. Let me know if you need any modifications!