Floyd Warshall

Problem

You are given an weighted directed graph, represented by an adjacency matrix, dist[][] of size n x n, where dist[i][j] represents the weight of the edge from node i to node j. If there is no direct edge, dist[i][j] is set to a large value (i.e., 10⁸) to represent infinity.
The graph may contain negative edge weights, but it does not contain any negative weight cycles.

Your task is to find the shortest distance between every pair of nodes i and j in the graph.

Note: Modify the distances for every pair in place.

Examples :

Input: dist[][] = [[0, 4, 108, 5, 108], [108, 0, 1, 108, 6], [2, 108, 0, 3, 108], [108, 108, 1, 0, 2], [1, 108, 108, 4, 0]]

Output: [[0, 4, 5, 5, 7], [3, 0, 1, 4, 6], [2, 6, 0, 3, 5], [3, 7, 1, 0, 2], [1, 5, 5, 4, 0]]

Explanation: Each cell dist[i][j] in the output shows the shortest distance from node i to node j, computed by considering all possible intermediate nodes.

Input: dist[][] = [[0, -1, 2], [1, 0, 108], [3, 1, 0]]

Output: [[0, -1, 2], [1, 0, 3], [2, 1, 0]]

Explanation: Each cell dist[i][j] in the output shows the shortest distance from node i to node j, computed by considering all possible intermediate nodes.
From 2 to 0 shortest distance should be 2 by following path 2 -> 1 -> 0
From 1 to 2 shortest distance should be 3 by following path 1 -> 0 -> 2

Constraints:
1 ≤ dist.size() ≤ 100
-1000 ≤ dist[i][j] ≤ 1000
dist[i][j] can be 10⁸ to represent infinity.

Solution

This algorithm is essentially a brute force method for calculating the shortest path between any two nodes.

• Floyd Warshall Algorithm

  • Used to find the shortest paths between all pairs of nodes in a graph.

  • It is a multisource shortest path algorithm.

  • Can detect negative cycles in the graph.

  • Works by considering each node as an intermediate point and updating the shortest paths.

• Algorithm Steps:

  1. Initialize the solution matrix the same as the input graph matrix.

  2. For each node k in the graph:

     • For each pair of nodes i and j:

       • Update dist[i][j] to be the minimum of dist[i][j] and dist[i][k] + dist[k][j].

  3. This process ensures that the shortest path for any two nodes is calculated by considering all possible intermediate nodes.

• Note:

  • The algorithm modifies the distances for every pair in place.

  • It goes through every node and calculates the shortest path each time, ensuring the shortest path for any two specific nodes in the graph.

Time - O(N³)

Space - O(NxN)

class Solution {
    public void floydWarshall(int[][] dist) {
        int n = dist.length;  
        for(int via=0; via<n; via++){

            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(dist[i][via] == 1e8 || dist[via][j]==1e8) continue;
                    dist[i][j] = Math.min(dist[i][j], dist[i][via]+dist[via][j]);
                }
            }
        }

    }
}