Floyd-Warshall algorithm

Write a program to implement the Floyd-Warshall algorithm

Example 1:

Input: n=6,edges={{1,2,10},{2,1,10},{2,3,5},{3,2,5},{1,3,35},{3,1,35},{1,6,50},{6,1,50},{6,2,50},{4,3,25},{5,3,5},{5,4,6},{2,6,10},{3,4,25},{3,5,5},{4,5,6}                                                                    

Output

0 10 15 26 20 20 
10 0 5 16 10 10 
15 5 0 11 5 15 
26 16 11 0 6 26 
20 10 5 6 0 20 
20 10 15 26 20 0

Approach: 

Java

import java.util.ArrayList;

public class FloydWarshallAlgorithm {
    public static void main(String[] args) {
        int n = 6;
        // all edges in the graph
        // graph is undirected
        ArrayList<Edge> edges = new ArrayList<>();
        addEdge(edges, 1, 2, 10);
        addEdge(edges, 2, 1, 10);
        addEdge(edges, 2, 3, 5);
        addEdge(edges, 3, 2, 5);
        addEdge(edges, 1, 3, 35);
        addEdge(edges, 3, 1, 35);
        addEdge(edges, 1, 6, 50);
        addEdge(edges, 6, 1, 50);
        addEdge(edges, 6, 2, 10);
        addEdge(edges, 4, 3, 25);
        addEdge(edges, 5, 3, 5);
        addEdge(edges, 5, 4, 6);
        addEdge(edges, 2, 6, 10);
        addEdge(edges, 3, 4, 25);
        addEdge(edges, 3, 5, 5);
        addEdge(edges, 4, 5, 6);

        int distance[][] = floyedWarshall(edges, n);
        // iterate from start edge to max edge
        System.out.println("Distance is :- ");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(distance[i][j] + "  ");
            }
            System.out.println();
        }
    }

    private static int[][] floyedWarshall(ArrayList<Edge>
                             edges, int n) {

        // vector to store the distance
        // of all nodes initialize with INT_MAX(infinite)
        int distance[][] = new int[n + 1][n + 1];

        // Initialize all the distance as infinite
        // and self as 0
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j)
                    distance[i][j] = Integer.MAX_VALUE;
                else
                    distance[i][j] = 0;
            }
        }

        for (int i = 0; i < edges.size(); i++) {
            int a = edges.get(i).a;
            int b = edges.get(i).b;
            int w = edges.get(i).w;
            // covert the vertex from 0 to n-1
            a--;
            b--;

            // add edge with weight into
            // the dist array
            distance[a][b] = w;
            distance[b][a] = w;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (distance[j][i] < Integer.MAX_VALUE 
                       && distance[i][k] < Integer.MAX_VALUE) {

                        // update distance of the node
                        // as min of previous and after include that vertex
                        // as intermediate
                        distance[j][k] = Math.min(distance[j][k],
                         distance[j][i] + distance[i][k]);
                    }
                }
            }
        }

        return distance;
    }

    // method for add edges into adj
    private static void addEdge(ArrayList<Edge> edges,
             int a, int b, int w) {
        edges.add(new Edge(a, b, w));
    }
}

// Edge classes
class Edge {
    int a;
    int b;
    int w;

    public Edge(int a, int b, int w) {
        super();
        this.a = a;
        this.b = b;
        this.w = w;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
#define INF 9999999

//function to find the all pair shortest
//path 
void floyedWarshall(int dist[][6],int n)
{
   for(int k=0;k<n;k++)
      {
        for(int i=0;i<n;i++)
           {
            for(int j=0;j<n;j++)
                {
                 if(dist[i][k]<INF &&dist[k][j]<INF)
                   {

                     //update distance of the node
                     //as min of previous and after include that vertex
                     //as intermediate      
                     dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
                    }
                }
            }
     }
}
int main()
{
    int n=6;
    int dist[6][6];
    //all edges in the graph 
    //graph is undirected
     vector<vector<int>> edges={{1,2,10},{2,1,10},{2,3,5},
                             {3,2,5},{1,3,35},{3,1,35},
                             {1,6,50},{6,1,50},{6,2,10},
                             {4,3,25},{5,3,5},{5,4,6},
                             {2,6,10},{3,4,25},{3,5,5},
                             {4,5,6}};
   //initailize all the distance as infinite
   // and self as 0
    for(int i=0;i<n;i++)
     {
       for(int j=0;j<n;j++)
         {
             if(i!=j)
                dist[i][j]=INF;
             else
               dist[i][j]=0;
         }    
     }
     for(int i=0;i<edges.size();i++)
       {
           int a=edges[i][0];
           int b=edges[i][1];
           int w=edges[i][2];
          //covert the vertex from 0 to n-1
           a--;
           b--;

           //add edge with weight into
           //the dist array
           dist[a][b]=w;
           dist[b][a]=w;
       }
  //call the floyed warshall algorithm
   floyedWarshall(dist,n);

 //print the distance for
 //all pair shortest paths
  for(int i=0;i<n;i++)
     {
         for(int j=0;j<n;j++)
             {
                 if(dist[i][j]==INF)
                    cout<<"INF ";
                 else
                    cout<<dist[i][j]<<" ";
                 
             }
         cout<<"\n";
     }
    return 0;
}
//Time Complexity: O(n^3)