// 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 java.util.LinkedList;
import com.graphs.GraphEdgeListRepresentation.Edge;
package com.graphs;



/**
 * Given a graph G and a vertex S, we want to find the shortest path from S to
 * any other vertex. Here we use the Bellman Ford algorithm.
 * 
 * @author STEPHANE MIGUEL KAKANAKOU (Skakanakou@gmail.com)
 *
 */
public class ShortestPathWithBellmanFord {

    /*** The Source vertex */
    private int S;

    /*** Array that contains the distance from the source to other vertices */
    private int[] dist;

    /*** Array that contains the path from the source to other vertices */
    private int[] prev;

    /**
     * Constructor that take the graph and the source vertex.
     * 
     * @param graph
     * @param S
     * @exception throw
     *                IllegalArgumentException if the given graph contains
     *                negative edge weight.
     */
    public ShortestPathWithBellmanFord(GraphEdgeListRepresentation graph, int S) {
        int v_size = graph.getV_Size();
        if ((S < 0) || (S >= v_size))
            throw new IllegalArgumentException("Invalid Argument");
        this.S = S;
        dist = new int[v_size];
        prev = new int[v_size];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);

        bellManFord(graph);

    }

    /*
     * Private method that perform the Bellman-Ford algorithm.
     */
    private void bellManFord(GraphEdgeListRepresentation graph) {
        dist[S] = 0;
        int v_size = graph.getV_Size();
        for (int i = 0; i < v_size - 1; i++) {
// 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/ShortestPathWithBellmanFord.java
import java.util.Arrays;
import java.util.LinkedList;
import com.graphs.GraphEdgeListRepresentation.Edge;

package com.graphs;



/**
 * Given a graph G and a vertex S, we want to find the shortest path from S to
 * any other vertex. Here we use the Bellman Ford algorithm.
 * 
 * @author STEPHANE MIGUEL KAKANAKOU (Skakanakou@gmail.com)
 *
 */
public class ShortestPathWithBellmanFord {

    /*** The Source vertex */
    private int S;

    /*** Array that contains the distance from the source to other vertices */
    private int[] dist;

    /*** Array that contains the path from the source to other vertices */
    private int[] prev;

    /**
     * Constructor that take the graph and the source vertex.
     * 
     * @param graph
     * @param S
     * @exception throw
     *                IllegalArgumentException if the given graph contains
     *                negative edge weight.
     */
    public ShortestPathWithBellmanFord(GraphEdgeListRepresentation graph, int S) {
        int v_size = graph.getV_Size();
        if ((S < 0) || (S >= v_size))
            throw new IllegalArgumentException("Invalid Argument");
        this.S = S;
        dist = new int[v_size];
        prev = new int[v_size];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);

        bellManFord(graph);

    }

    /*
     * Private method that perform the Bellman-Ford algorithm.
     */
    private void bellManFord(GraphEdgeListRepresentation graph) {
        dist[S] = 0;
        int v_size = graph.getV_Size();
        for (int i = 0; i < v_size - 1; i++) {
            for (Edge edge : graph.getEdgeslist()) {