Floyd Warshall

Problem Statement

All pair shortest Paths

Intuition

Tc = V^3

Links

https://practice.geeksforgeeks.org/problems/implementing-floyd-warshall2042/1

Video Links

https://www.youtube.com/watch?v=YbY8cVwWAvw&ab_channel=takeUforward

Approach 1:

C++

//User function template for C++

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

        
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems