// Path: Java-data-Structures/src/main/java/com/graphs/GraphEdgeListRepresentation.java
// public static class Edge implements Comparable<Edge> {
//     int u;
//     int v;
//     int w;
// 
//     public Edge(int begin, int end) {
//         this.u = begin;
//         this.v = end;
//         this.w = 1;
//     }
// 
//     public Edge(int begin, int end, int weight) {
//         this.u = begin;
//         this.v = end;
//         this.w = weight;
//     }
// 
//     @Override
//     public int hashCode() {
//         final int prime = 31;
//         int result = 1;
//         result = prime * result + u;
//         result = prime * result + v;
//         return result;
//     }
// 
//     @Override
//     public boolean equals(Object obj) {
//         if (this == obj)
//             return true;
//         if (obj == null)
//             return false;
//         if (getClass() != obj.getClass())
//             return false;
//         Edge other = (Edge) obj;
//         if (u != other.u)
//             return false;
//         if (v != other.v)
//             return false;
//         return true;
//     }
// 
//     @Override
//     public String toString() {
//         return "Edge [u=" + u + ", v=" + v + ", w=" + w + "]";
//     }
// 
//     @Override
//     public int compareTo(Edge other) {
//         if (this.w < other.w)
//             return -1;
//         else if (this.w > other.w)
//             return 1;
//         else
//             return 0;
//     }
// }


import java.util.Arrays;
import com.graphs.GraphEdgeListRepresentation.Edge;
package com.graphs;



/**
 * Given a graph G, we want to find the shortest path between any two vertices.
 * For that we use the Floyd Warshall algorithm.
 * 
 * @author STEPHANE MIGUEL KAKANAKOU (Skakanakou@gmail.com)
 *
 */
public class AllShortestPathWithFloydWarshall {

    /*** Array that contains all shortest path distance */
    private int[][] dist;

    /**
     * Constructor that take the graph and compute all shortest path.
     * 
     * @param graph
     * @exception throw
     *                IllegalArgumentException if the given graph contains
     *                negative edge weight.
     */
    public AllShortestPathWithFloydWarshall(GraphEdgeListRepresentation graph) {
        int v_size = graph.getV_Size();
        dist = new int[v_size][v_size];

        floydWarshall(graph);

    }

    /*
     * Private method that perform the Floyd Warshall algorithm.
     */
    private void floydWarshall(GraphEdgeListRepresentation graph) {
        int v_size = graph.getV_Size();

        for (int i = 0; i < v_size; i++)
            Arrays.fill(dist[i], Integer.MAX_VALUE);

        for (int i = 0; i < v_size; i++)
            dist[i][i] = 0;

// Path: Java-data-Structures/src/main/java/com/graphs/GraphEdgeListRepresentation.java
// public static class Edge implements Comparable<Edge> {
//     int u;
//     int v;
//     int w;
// 
//     public Edge(int begin, int end) {
//         this.u = begin;
//         this.v = end;
//         this.w = 1;
//     }
// 
//     public Edge(int begin, int end, int weight) {
//         this.u = begin;
//         this.v = end;
//         this.w = weight;
//     }
// 
//     @Override
//     public int hashCode() {
//         final int prime = 31;
//         int result = 1;
//         result = prime * result + u;
//         result = prime * result + v;
//         return result;
//     }
// 
//     @Override
//     public boolean equals(Object obj) {
//         if (this == obj)
//             return true;
//         if (obj == null)
//             return false;
//         if (getClass() != obj.getClass())
//             return false;
//         Edge other = (Edge) obj;
//         if (u != other.u)
//             return false;
//         if (v != other.v)
//             return false;
//         return true;
//     }
// 
//     @Override
//     public String toString() {
//         return "Edge [u=" + u + ", v=" + v + ", w=" + w + "]";
//     }
// 
//     @Override
//     public int compareTo(Edge other) {
//         if (this.w < other.w)
//             return -1;
//         else if (this.w > other.w)
//             return 1;
//         else
//             return 0;
//     }
// }


// Path: Java-data-Structures/src/main/java/com/graphs/AllShortestPathWithFloydWarshall.java
import java.util.Arrays;
import com.graphs.GraphEdgeListRepresentation.Edge;

package com.graphs;



/**
 * Given a graph G, we want to find the shortest path between any two vertices.
 * For that we use the Floyd Warshall algorithm.
 * 
 * @author STEPHANE MIGUEL KAKANAKOU (Skakanakou@gmail.com)
 *
 */
public class AllShortestPathWithFloydWarshall {

    /*** Array that contains all shortest path distance */
    private int[][] dist;

    /**
     * Constructor that take the graph and compute all shortest path.
     * 
     * @param graph
     * @exception throw
     *                IllegalArgumentException if the given graph contains
     *                negative edge weight.
     */
    public AllShortestPathWithFloydWarshall(GraphEdgeListRepresentation graph) {
        int v_size = graph.getV_Size();
        dist = new int[v_size][v_size];

        floydWarshall(graph);

    }

    /*
     * Private method that perform the Floyd Warshall algorithm.
     */
    private void floydWarshall(GraphEdgeListRepresentation graph) {
        int v_size = graph.getV_Size();

        for (int i = 0; i < v_size; i++)
            Arrays.fill(dist[i], Integer.MAX_VALUE);

        for (int i = 0; i < v_size; i++)
            dist[i][i] = 0;

        for (Edge edge : graph.getEdgeslist())