Floyd Warshall Algorithm (Multi-source shorted path)

Floyd Warshall algorithm

This is bit different from dijikstra's or bellman ford algorithm,
Floyd warshall helps in getting shorted path from all vertices( as source) to all the other vertices in the graph.
It also helps in detecting negative cycle in the graph.
What is shorted path?: Any path that takes least amount of edge weights is called shorted path for the given source and destination node.
Go via every vertex to find the shorted path for the given source and the destination.

//tc : O(n^3) cubic operation, sc : (n^2) for using matrix (since we are using it to store further values 
//while we are solving the prolem, like dp

class Solution
{
    public void shortest_distance(int[][] matrix)
    {
        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] = (int)1e9;
                }
                if(i ==j){
                    matrix[i][j] = 0; //disntace of node n from node n will be 0
                }
            }
        }
        for(int k = 0;k<n;k++){
            for(int i =0;i<n;i++){
                for(int j =0;j<n;j++){
                    matrix[i][j] = Integer.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
                }
            }
        }

        // checking for negative edge cycle
//negative edge cycle: when the sum of edge weights of all the edges in the cycle in negative( for more understanding refer this : https://youtu.be/YbY8cVwWAvw?list=PLgUwDviBIf0oE3gA41TKO2H5bHpPd7fzn&t=1382)
        for(int i =0;i<n;i++){
            for(int j =0;j<n;j++){
                if(matrix[i][j] < 0){
                   // it means that the graph has negative edge cycle in it
                }
            }
        }
        for(int i =0;i<n;i++){
            for(int j =0;j<n;j++){
                if(matrix[i][j] ==(int)1e9){
                    matrix[i][j] = -1;
                }
            }
        }

    }
}

Find the city with the smallest number of neighbors having threshold distance

Intuition

We have to find distance of all the nodes from all the nodes i.e
Multisource shortest path

Approach

Floyd Warshall algorithm

Complexity

• Time complexity:
  O(n^3)

• Space complexity:
  O(n^2) for using matrix

Code

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int matrix[][] = new int[n][n];
//initiaze adjacency matrix
         for(int i =0;i<n;i++){
            for(int j =0;j<n;j++){
                if(i ==j) matrix[i][j] = 0; // distance between same nodes should be 0
                else matrix[i][j] = (int)1e9; 
            }
        }
// preparing adjacency matrix
        for(int i =0;i<edges.length;i++){
            int I = edges[i][0];
            int J = edges[i][1];
            int W = edges[i][2];
            matrix[I][J] = W;
            matrix[J][I] = W;
        }

        //O(n^3)
        //finding distance of every node from every other node
        for(int k =0;k<n;k++){
            for(int i =0;i<n;i++){
                for(int j =0;j<n;j++){
                    //distance between node i and j via k
                    matrix[i][j] = Integer.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
                }
            }
        }
        int node = 0;
        int minCount = Integer.MAX_VALUE;
        for(int i =0;i<n;i++){
            int count =0;
            for(int j = 0;j<n;j++){
                if(matrix[i][j] <=distanceThreshold){
                    count++;
                }
            }
            if(minCount > count){
                minCount = count;
                node = i;
            }
            else if(minCount ==count){
                node = Integer.max(node,i);
            }
        }
        return node;
    }
}