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;
}
}
Top comments (0)