Skip to main content

Floyd Warshall Algorithm

Problem​

The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph. The Graph is represented as adjancency matrix, and the matrix denotes the weight of the edegs (if it exists) else -1. Do it in-place.

Solution Approach​

Expected Time complexity: O(n3)O(n^3)

Click - to see solution code
class Solution {
   public:
    void shortest_distance(vector<vector<int>>& matrix) {
        int v = matrix.size();
        for (int k = 0; k < v; k++) {      // vertex as intermediate
            for (int i = 0; i < v; i++) {  // all vertex as source one by one
                for (int j = 0; j < v; j++) {  // destination
                    if (matrix[i][k] == -1 || matrix[k][j] == -1) {
                        continue;
                    }
                    int cur = matrix[i][k] + matrix[k][j];

                    if (matrix[i][j] == -1) {
                        matrix[i][j] = cur;
                    }

                    else
                        matrix[i][j] = min(matrix[i][j], cur);
                }
            }
        }
    };