import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class FloydWarshallParallel {
    private static final int INF = Integer.MAX_VALUE / 2; // To avoid integer overflow

    public static void main(String[] args) throws InterruptedException {
        // Example graph represented as an adjacency matrix
        int[][] graph = {
            {0, 5, INF, 10},
            {INF, 0, 3, INF},
            {INF, INF, 0, 1},
            {INF, INF, INF, 0}
        };

        floydWarshallParallel(graph);
        printGraph(graph);
    }

    private static void floydWarshallParallel(int[][] dist) throws InterruptedException {
        int n = dist.length;
        ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

        for (int k = 0; k < n; k++) {
            final int finalK = k;
            for (int i = 0; i < n; i++) {
                final int finalI = i;
                executor.submit(() -> {
                    for (int j = 0; j < n; j++) {
                        if (dist[finalI][finalK] != INF && dist[finalK][j] != INF) {
                            dist[finalI][j] = Math.min(dist[finalI][j], dist[finalI][finalK] + dist[finalK][j]);
                        }
                    }
                });
            }
            executor.awaitTermination(1, TimeUnit.SECONDS);
        }
        executor.shutdown();
        executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
    }

    private static void printGraph(int[][] graph) {
        int n = graph.length;
        System.out.println("Shortest distances between every pair of vertices:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == INF)
                    System.out.print("INF ");
                else
                    System.out.print(graph[i][j] + "   ");
            }
            System.out.println();
        }
    }
}