Day 41: Floyd Warshall

/*
Floyd Warshall

Lamp
This problem is part of GFG SDE Sheet. Click here to view more.  

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 of size n*n. Matrix[i][j] denotes the weight of the edge from i to j. If Matrix[i][j]=-1, it means there is no edge from i to j.
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 2 from 0 as 0->1->2
and the cost will be 1+6=7 which is less than 
43.
Your Task:
You don't need to read, return or print anything. Your task is to complete the function shortest_distance() which takes the matrix as input parameter and modifies the distances for every pair in-place.

Expected Time Complexity: O(n3)
Expected Space Complexity: O(1)

Constraints:
1 <= n <= 100
-1 <= matrix[ i ][ j ] <= 1000
*/


//{ Driver Code Starts
//Initial template for JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while(T-->0)
        {
            int n = Integer.parseInt(br.readLine().trim());
            int[][] matrix = new int[n][n];
            for(int i = 0; i < n; i++){
                String[] s = br.readLine().trim().split(" ");
                for(int j = 0; j < n; j++)
                    matrix[i][j]  =Integer.parseInt(s[j]);
            }
            Solution obj = new Solution();
            obj.shortest_distance(matrix);
            for(int i = 0; i < n; i++){
                for(int j  = 0; j < n; j++){
                    System.out.print(matrix[i][j] + " ");
                }
                System.out.println();
            }
        }
    }
}

// } Driver Code Ends


//User function template for JAVA

class Solution
{
    public void shortest_distance(int[][] matrix)

    {

        // Code here 

        int n = matrix.length;

        for(int i=0; i<n; i++){

            for(int j=0; j<n; j++){

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

                    matrix[i][j]= Integer.MAX_VALUE;

                }

            }

        }

        for(int k=0; k<n; k++){

            for(int i=0; i<n; i++){

                for(int j=0; j<n; j++){

                   if(matrix[i][k]< Integer.MAX_VALUE && matrix[k][j]< Integer.MAX_VALUE){

                     matrix[i][j]= Math.min(matrix[i][j], matrix[i][k]+ matrix[k][j]);

                   } 

                }

                

            }

        }

        for(int i=0; i<n; i++){

            for(int j=0; j<n; j++){

                if(matrix[i][j]==Integer.MAX_VALUE){

                    matrix[i][j]= -1;

                }

            }

        }

    }
}