All Pairs Shortest Path

  Explanation Video

Java Program

/* package codechef; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* All Pairs Shortest Path (Floyd-Warshall) - Dynamic Programming. */

class AllPairsShortestPath {

    // Find shortest path

    private static int[][] floydWarshall() {

        // Get input graph

        int[][] graph = populateGraph();

        

        // Size of the graph

        int size = graph.length;

        

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

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

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

                    // Perform operation if it do not have INFINITE

                    if(graph[i][k] + graph[k][j] >= 0) {

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

                    }

                }

            }

        }

        

        return graph;

    }

    

    

    // Populate graph. Values can be inserted from any source ie. keyboard

    private static int[][] populateGraph() {

        // Taking max Integer value to represent INFINITE

        int INF = Integer.MAX_VALUE;

        int[][] graph = {

            {0,3,INF,7},

            {8,0,2,INF},

            {5,INF,0,1},

            {2,INF,INF,0}

        };

        return graph;

    }

public static void main (String[] args) {

int[][] graph = floydWarshall();

for(int i = 0; i < graph.length; i++) {

            for(int j = 0; j < graph.length; j++) {

                System.out.print(graph[i][j] + " ");

            }

            System.out.println();

        }

}

}

Time Complexity O(N^3)

GreeksForGreeks