Shortest Path: Floyd Warshall Algorithm

MULTI SOURCE ALGORITHM

The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed graph. The graph is represented as an adjacency matrix. mat[i][j] denotes the weight of the edge from i to j. If mat[i][j] = -1, it means there is no edge from i to j. Note: Modify the distances for every pair in place.

Practice Link

Doesn't work for negative edge cycle

Intiution#

Floyd-Warshall is a dynamic programming approach: the shortest path from i to j either does not pass through vertex k, or it passes through k as an intermediate — in which case the cost is the cost from i to k plus the cost from k to j. By iterating k from 0 to V-1 and updating all pairs, we progressively consider every possible intermediate vertex, converging on the globally optimal paths for every source-destination pair.

For every pair of vertices i and j, there will be k vertex as intermediate in the path.

Alogrithm#

Pre-requisites

1. if there is no edge between i and j , mat[i][j] = INF
2. if i==j, mat[i][j] = 0

For every intermediate vertex k (outer loop), iterate over all source-destination pairs (i, j) and relax the distance:

mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

The outer loop over k must be the outermost — this ensures that when we use k as an intermediate, paths through all earlier intermediates (0 to k-1) are already optimally computed. We maintain a V×V matrix updated in-place.

Implementation#

class Solution {
  public:
    void shortestDistance(vector<vector<int>>& mat) {
        int V = mat.size();
        
        for(int i=0;i<V;i++)
        {
            for(int j=0;j<V;j++)
            {
                if(mat[i][j]==-1)
                    mat[i][j] = 1e9;
                if(i==j)
                    mat[i][j]=0;
            }
            
        }
        
        for(int k=0;k<V;k++)
        {
            for(int i=0;i<V;i++)
            {
                for(int j=0;j<V;j++)
                {
                        mat[i][j] = min(mat[i][j],mat[i][k]+mat[k][j]);
                }
            }
        }
        for(int i=0;i<V;i++)
        {
            for(int j=0;j<V;j++)
            {
                if(mat[i][j]==1e9)
                    mat[i][j] = -1;
            }
            
        }
        
    }
};

Time Complexity: O(V^3 )

Space Complexity: O(V^2 )