import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;


class Vertex<E extends Comparable<E>> implements Comparable<Vertex<E>>{  // E data
    private E data;
    private double minDistance;
    private Vertex predecessor;

    public Vertex(E data,double minDistance,Vertex predecessor){
        this.data = data;
        this.minDistance = minDistance;
        this.predecessor = predecessor;
    }

    public Vertex(E data,double minDistance){
        this.data = data;
        this.minDistance = minDistance;
        this.predecessor = null;
    }

    public Vertex(E data){
        this.data = data;
        this.minDistance = Double.MAX_VALUE;
        this.predecessor = null;
    }

    public boolean hasPredecessor(){
        return this.predecessor != null;
    }

    public double getMinDistance() {
        return minDistance;
    }

    public void setMinDistance(double minDistance) {
        this.minDistance = minDistance;
    }

    public Vertex<E> getPredecessor() {
        return predecessor;
    }

    public void setPredecessor(Vertex predecessor) {
        this.predecessor = predecessor;
    }

    public E getData() {
        return data;
    }

    public void setData(E data) {
        this.data = data;
    }

    @Override
    public int compareTo(Vertex<E> v) {
        return Double.compare(minDistance, v.getMinDistance());
    }

    @Override
    public int hashCode() {
        int hash = 3;
        hash = 29 * hash + Objects.hashCode(this.data);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Vertex<E> other = (Vertex<E>) obj;
        if (!this.data.equals(other.data)) {
            return false;
        }
        return true;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("Vertex with data: " + this.data + " minDist: " + this.minDistance + " Pred: " + this.predecessor);
        return sb.toString();
    }

}

class Edge<E extends Comparable<E>>{
    private Vertex<E> source;
    private Vertex<E> destination;
    private double weight;

    public Edge(Vertex<E> source, Vertex<E> destination, double weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }

    public Vertex<E> getSource() {
        return source;
    }

    public void setSource(Vertex<E> source) {
        this.source = source;
    }

    public Vertex<E> getDestination() {
        return destination;
    }

    public void setDestination(Vertex<E> destination) {
        this.destination = destination;
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double weight) {
        this.weight = weight;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("Edge from: ").append(this.source.toString())
                .append("\nTo: ").append(this.destination.toString())
                .append("\nWith weight: " + this.weight);
        return sb.toString();
    }



}
class Graph<E extends Comparable<E>>{

    List<Vertex<E>> vertices;
    List<Edge<E>> edges;
    Map<E,Integer> indexes; // Integer : na koe mesto vo listata e

    public Graph(){
        vertices = new ArrayList<>();
        edges = new ArrayList<>();
        indexes = new HashMap<>();
    }

    public void addVertex(E data){
        Vertex<E> vertex = new Vertex<>(data);
        vertices.add(vertex);
        int index = vertices.size() - 1;
        indexes.put(data, index);
    }

    public Vertex<E> getVertex(E data){
       return vertices.get(indexes.get(data));
    }

    private boolean addEdge(Vertex<E> source,Vertex<E> destination,double weight){
        return edges.add(new Edge<E>(source,destination,weight));
    }

    public boolean addEdge(E source,E destination,double weight){
        Vertex<E> s = vertices.get(indexes.get(source));
        Vertex<E> d = vertices.get(indexes.get(destination));
        return addEdge(s,d,weight);
    }
    public boolean addEdgeBeetween(E source,E destination,double weight){
        Vertex<E> s = vertices.get(indexes.get(source));
        Vertex<E> d = vertices.get(indexes.get(destination));

        return addEdge(s,d,weight) && addEdge(d,s,weight);
    }

    public List<Vertex<E>> getVertices(){
        return this.vertices;
    }

    public List<Edge<E>> getEdges(){
        return this.edges;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        for (Vertex<E> v : this.getVertices()){
            sb.append(v.toString() + "\n");
        }
        return sb.toString();
    }

    public double getMinDistanceBetweenDijkstra(E start,E end){
        Vertex<E> source = vertices.get(indexes.get(start));
        Vertex<E> destination = vertices.get(indexes.get(end));
        Dijkstra<E> dijkstra = new Dijkstra<>();

        dijkstra.run(this, source);

        return destination.getMinDistance();
    }

    public double getMinDistanceBetweenBellmanFord(E start,E end){
        Vertex<E> source = vertices.get(indexes.get(start));
        Vertex<E> destination = vertices.get(indexes.get(end));

        BellmanFord<E> bellmanFord = new BellmanFord<>();

        if (bellmanFord.run(this, source))
            return destination.getMinDistance();

        else
            return -1;
    }
}

class Dijkstra<E extends Comparable<E>>{

    public Dijkstra(){
    }

    private Hashtable<Vertex<E>, List<Edge<E> > > makeHashtable(Graph<E> graph){
            Hashtable<Vertex<E>, List<Edge<E> > > table = new Hashtable<>();
            List<Edge<E>> lst;
            for (Vertex<E> v : graph.getVertices()){
                lst = new LinkedList<>();
                table.put(v,lst);
            }

            for (Edge<E> e : graph.getEdges()){
                table.get(e.getSource()).add(e);
            }

            return table;
        }
    public void run(Graph<E> graph, Vertex<E> startVertex){

        if (graph == null || startVertex == null)
        return;

        for (Vertex<E> v : graph.getVertices()){
            v.setMinDistance(Double.MAX_VALUE);
            v.setPredecessor(null);
        }

        startVertex.setMinDistance(0d);
        PriorityQueue<Vertex<E>> queue = new PriorityQueue<>(graph.getVertices());
        Hashtable<Vertex<E>, List<Edge<E>>> table = makeHashtable(graph);

        while (!queue.isEmpty()){
            Vertex<E> u = queue.poll();

            for (Edge<E> e : table.get(u)){
                Vertex<E> v = e.getDestination();
                if (v.getMinDistance() > u.getMinDistance() + e.getWeight()){
                    v.setMinDistance(u.getMinDistance() + e.getWeight());
                    v.setPredecessor(u);
                    queue.add(v);
                }
            }
        }

    }

}

class BellmanFord<E extends Comparable<E>>{

    private void relax(Edge<E> edge){
        if (edge.getDestination().getMinDistance() > edge.getSource().getMinDistance() + edge.getWeight()){
            edge.getDestination().setMinDistance(edge.getSource().getMinDistance() + edge.getWeight());
            edge.getDestination().setPredecessor(edge.getSource());
        }
    }
    public boolean run(Graph<E> graph, Vertex<E> startVertex){
        if (graph == null || startVertex == null)
        return false;

        for (Vertex<E> v : graph.getVertices()){
            v.setMinDistance(Double.MAX_VALUE);
            v.setPredecessor(null);
        }

        startVertex.setMinDistance(0d);

        for (int i = 0; i < graph.getVertices().size(); i++){
            for (Edge<E> edge : graph.getEdges()){
                relax(edge);
            }
        }

        for (Edge<E> edge : graph.getEdges()){
            if (edge.getDestination().getMinDistance() > edge.getSource().getMinDistance() + edge.getWeight()){
                return false;
            }
        }

        return true;
    }
}
public class Main{

 public static void main(String[] args){
        Graph<String> graph = new Graph<>();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");


        graph.addEdge("A","B",4);
        graph.addEdge("A","C",2);
        graph.addEdge("B","C",3);
        graph.addEdge("C","B",1);
        graph.addEdge("B","D",2);
        graph.addEdge("B","E",3);
        graph.addEdge("C","E",5);
        graph.addEdge("C","D",4);
        graph.addEdge("E","D",1);

        System.out.println(graph.getMinDistanceBetweenBellmanFord("A", "D"));
        Vertex<String> current = graph.getVertex("D");
        while(current.hasPredecessor()){
            System.out.println(current);
            current = current.getPredecessor();
        }

    }

}