All Pairs Shortest Path - Floyd Warshall Algorithm

 Click Me
 
What is All Pairs Shortest Path (APSP)? 
  • It calculates the shortest distance between each pair of vertices/nodes of the graph.
  • We can also implement APSP by BFS, Dijkstra's Algorithm and Bellman-Ford Algorithm by running these algorithms for all the vertices/nodes in the graph/
  • Here we will be discussing a new algorithm for calculating only All Pairs Shortest Path. That means it can't be used to find the Single Source Shortest Path. The name of the algorithm is the Floyd Warshall Algorithm. 
  • The Floyd Warshall Algorithm does not work for / detects a negative cycle.

Floyd Warshall Algorithm [Time Complexity: O(V^3) , Space Complexity: O(V^2)]
1. Initialize a square matrix (adjacency matrix):
        a. If i==j , put 0 in that cell
        b. Else if there is a direct edge from node i to node j then we put the weight of that edge in that cell.
        c. Else if there is no direct edge, we put infinity in that cell

2. for every vertex/node in the node list  (taken as intermediate vertex):
        3. for each cell in the adjacency matrix, check if there is a shorter path from the current source to the current destination via the current intermediate vertex :
                    4. if a[i][j] > a[i][k] + a[k][j]  , that is i->k->j where i is source, k is current intermediate vertex and j is destination, update the cell -> a[i][j] = a[i][k] + a[k][j]

3. Print the adjacency matrix that will now represent the shortest distance between all pairs of vertices/nodes of the graph.



import java.util.*;

// A Graph Node
class GraphNode{
    String name;
    
    // Neigbours list
    ArrayList<GraphNode> neighbours;
    // edge (to neighbours) weight map
    HashMap<GraphNode,Integer> weightMap;
    
    // Constructor
    GraphNode(String name){
        this.name = name;
        this.neighbours = new ArrayList<>();
        this.weightMap = new HashMap<>();
    }
}

public class Main {
    
    //List of Nodes in the graph
    ArrayList<GraphNode> nodesList;
    
    // Constructor
    Main(){
        this.nodesList = new ArrayList<>();
    }
    
    // Method to find All Pairs Shortest Path using Floyd Warshall
    public void floydWarshall(){
        
        int size = this.nodesList.size();
        // Making an adjacency list
        int[][] distanceMatix = new int[size][size];
        
        // for every pair of vertices initialize the distanceMatix
        for(int i=0;i<size;i++){
            GraphNode source = this.nodesList.get(i);
            for(int j=0;j<size;j++){
                GraphNode destination = this.nodesList.get(j);
                // if same vertex
                if(i==j){
                    distanceMatix[i][j]=0;
                }
                // if there is a direct edge from source vertex to destination vertex
                else if(source.weightMap.containsKey(destination)){
                    distanceMatix[i][j] = source.weightMap.get(destination);
                }
                // if there is no direct edge from source vertexx to destination node
                else{
                    // marking it as Integer.MAX_VALUE divided by 10 to avoid arithmetic overflow
                    distanceMatix[i][j] = Integer.MAX_VALUE/10;
                }
            }
        }
        
        // for every pair of vertices if the distance from i to j (distanceMatix[i][j]) is greater than distance from i to j through any intermediate vertex 'k', we update the distance
        // distanceMatix[i][j] -> distance from source vertex 'i' to destination vertex 'j'
        // distanceMatix[i][k] -> distance from source vertex 'i' to intermediate vertex 'k'
        // distanceMatix[k][j] -> distance from intermediate vertex 'k' to destination vertex 'j'
        // THE USE OF THIS FUNCTION IS ONLY TO CHECK THAT WHETHER THERE IS A NON-DIRECT BETTER PATH FROM SOURCE TO DESTINATION
        for(int k=0;k<size;k++){
            for(int i=0;i<size;i++){
                for(int j=0;j<size;j++){
                    // if we are calculating for kth vertex, so we need to to check our condition for updating distance for all those paths already including kth vertex
                    // That is we need not calculate for vertices in kth row and kth column
                    // for eg. if we are checking for node 0, then we skip all edges in 0th column and 0th row of adjacency matrix (here distanceMatix)
                    if(i==k || j==k){
                        continue;
                    }
                    else if(distanceMatix[i][j] > (distanceMatix[i][k] + distanceMatix[k][j])){
                        distanceMatix[i][j] = distanceMatix[i][k] + distanceMatix[k][j];
                    }
                }
            }
        }
        
        // Print Shortest distance between all pair of vertices
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                System.out.print(distanceMatix[i][j]+" ");
            }
            System.out.println();
        }
        
    }
    
    // helper function to add a directed weighted edge from node i to j, and having with weight of edge 'weight'
    private void addDirectedWeightedEdge(int i, int j, int weight){
        GraphNode src = this.nodesList.get(i-1);
        GraphNode dest = this.nodesList.get(j-1);
        src.neighbours.add(dest);
        src.weightMap.put(dest,weight);
    }
    
    public static void main(String[] args) throws Exception {
        Main graph = new Main();
        
        // adding 5 nodes V1-V5 to nodeList
        for(int i=1;i<=5;i++){
            graph.nodesList.add(new GraphNode("V"+i));
        }
        
        // Now adding directed weighted edges between nodes
        // Diagram for the graph used is on the top of post: 
                graph.addDirectedWeightedEdge(1,3,6); //Add V1 -> V3 , weight 6
graph.addDirectedWeightedEdge(1,4,6); //Add V1 -> V4 , weight 6
graph.addDirectedWeightedEdge(2,1,3); //Add V2 -> V1 , weight 3
graph.addDirectedWeightedEdge(3,4,2); //Add V3 -> V4 , weight 2
graph.addDirectedWeightedEdge(4,3,1); //Add V4 -> V3 , weight 1
graph.addDirectedWeightedEdge(4,2,1); //Add V4 -> V2 , weight 1
graph.addDirectedWeightedEdge(5,2,4); //Add V5 -> V2 , weight 4
graph.addDirectedWeightedEdge(5,4,2); //Add V5 -> V4 , weight 2
graph.floydWarshall();
    }
}


Output:

0 7 6 6 214748364 
3 0 9 9 214748364 
6 3 0 2 214748364 
4 1 1 0 214748364 
6 3 3 2 0

Comments

Post a Comment

Popular posts from this blog

Quick Sort

According to me, it is the easiest and one of the most important and efficient sorting algorithm. Java 7 also uses quicksort for their .sort() method Time Complexity - O(nlogn) Space Complexity - O(n) -> As we are using recursion, it uses the internal stack In quicksort, we chose a pivot element first (in this program, I chose the last element as pivot) All the elements in any array, which are less than the pivot remains to the left of pivot and all the elements which are greater than the pivot element remains to the right of pivot. To do the above, we first chose last element as pivot element, i as (start-1) and j as start In quicksort, we only have to take care of pivot, i and j Now, we compare if a[i]<= pivot element. If yes, we increment i and swap arr[i] and arr[j] After completing one iteration from start to end, we get a pivot element fixed at its right position. Now, we recursively do this for the left subarray and right subarray to the pivot element. QuickS...
Read more

Disjoint Set - Implemented Using Arrays

Image
  What is a Disjoint Set? Well, Wikipedia has the perfect definition -  A disjoint-set data structure (also called a union-find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses, disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph. The disjoint set has mainly 3 Operations: makeset() -> makes 'n' number of disjoint sets containing single elements find(currentSet) -> returns the representative/parent of currentSet union(set1,set2) -> merges two disjoint sets represented by set1 and set2 into a new disjoint set.  Before going through code, I would recommend watching this video -  https://www.youtube.com/watch?v=wU6udHRIkcc Code: public class Mai...
Read more

Graph Traversal Code - BFS on Graph represented using Adjacency Matrix

Image
  import java.util.*; // A graph Node class GraphNode{     String name;     boolean isVisited;     //index is used to map this node with index of Adjacency Matrix     int index;      GraphNode(String name,int index){         this.name = name;         this.isVisited = false;         this.index = index;     }      } public class Main {          // A List to store the address of all the nodes of the graph     ArrayList<GraphNode> nodeList = new ArrayList<GraphNode>();     // An adjacency Matrix to store the details about which nodes are adjacent to each other (basically which two nodes has a edge between them)     int [][] adjacencyMatrix;          // Constructor     Main(ArrayList<GraphNode> nodeList){         this.nod...
Read more