Problem Statement

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.

Example 1:

Input:matrix = {{0,25},{-1,0}}
Output:{{0,25},{-1,0}}
Explanation:The shortest distance between
every pair is already given(if it exists).

Example 2:

Input:matrix = {{0,1,43},{1,0,6},{-1,-1,0}}
Output:{{0,1,7},{1,0,6},{-1,-1,0}}
Explanation:We can reach 3 from 1 as 1->2->3
and the cost will be 1+6=7 which is less than
43.

Problem Link

Floyd Warshall | Practice | GeeksforGeeks

Reference Video

https://www.youtube.com/watch?v=nV_wOZnhbog&list=PLEJXowNB4kPzByLnnFYNSCoqtFz0VKLk5&index=25&ab_channel=TECHDOSETECHDOSE

Code

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