6. Floyd Warshal

// Floyd-Warshall Algorithm
// Finds the shortest distance between EVERY pair of vertices.
// Works with negative edge weights.
// Can also detect negative cycles.

vector<vector<int>> floydWarshall(int V, vector<vector<int>>& edges) {

    // Distance matrix
    // Initially, assume every node is unreachable.
    vector<vector<int>> dist(V, vector<int>(V, INT_MAX));

    // Distance from a node to itself is always 0.
    for (int i = 0; i < V; i++)
        dist[i][i] = 0;

    // Fill the direct edge weights.
    for (auto edge : edges) {

        int u = edge[0];
        int v = edge[1];
        int wt = edge[2];

        dist[u][v] = wt;

        // Uncomment for an undirected graph.
        // dist[v][u] = wt;
    }

    // Main Floyd-Warshall Algorithm
    // Try every vertex as an intermediate node.
    for (int k = 0; k < V; k++) {

        // Choose every possible source.
        for (int i = 0; i < V; i++) {

            // Choose every possible destination.
            for (int j = 0; j < V; j++) {

                // If either path doesn't exist,
                // we cannot go through k.
                if (dist[i][k] == INT_MAX ||
                    dist[k][j] == INT_MAX)
                    continue;

                // Relax the path.
                // Is going through k shorter?
                dist[i][j] = min(
                    dist[i][j],
                    dist[i][k] + dist[k][j]
                );
            }
        }
    }

    // Negative Cycle Detection
    // If the distance from a node to itself
    // becomes negative, a negative cycle exists.
    for (int i = 0; i < V; i++) {

        if (dist[i][i] < 0) {

            cout << "Negative Cycle Exists\n";

            // Handle according to the problem.
            // return {};
        }
    }

    // dist[i][j] now contains the shortest distance
    // from i to j.
    return dist;
}