C9

import java.util.*;
import sk.upjs.paz.graph.*;

public class BellmanFord {

        public static void relax(Edge e, Map<Vertex, Double> d,
                        Map<Vertex, Vertex> predchodcovia) {
                Vertex u = e.getSource();
                Vertex v = e.getTarget();
                if (d.get(u) + e.getWeight() < d.get(v)){
                        predchodcovia.put(v, u);//ak idem znizit dlzku tak aj pridam predchodcu
                        d.put(v, d.get(u) + e.getWeight());
                        }
        }

        public static Map<Vertex, Double> bellmanFord(Graph g, Vertex s) {
                Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY);
                Map<Vertex, Vertex> predchodcovia = g.createVertexMap(null);
                d.put(s, 0d);
                for (int i = 0; i < g.getVertices().size(); i++)
                        for (Edge e : g.getEdges())
                                relax(e, d, predchodcovia);
                System.out.println(predchodcovia);
                return d;
        }

        public static String cesta(Graph g, Vertex zaciatok, Vertex koniec) {
                Map<Vertex, Double> hodnoty = new HashMap<>();
                StringBuilder cesta = new StringBuilder();
                cesta.append(koniec);
                hodnoty = BellmanFord.bellmanFord(g, zaciatok);
                while (!zaciatok.equals(koniec)) {
                        for (Edge e : koniec.getEdges()) {
                                Vertex kam = e.getTarget();
                                if (kam.equals(koniec)) {
                                        kam = e.getSource();
                                }
                                if ((hodnoty.get(koniec) - e.getWeight()) == hodnoty.get(kam)) {
                                        koniec = kam;
                                        cesta.append(koniec);
                                        break;
                                }
                        }
                }
                cesta.reverse();
                return cesta.toString();
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub

                // Nacitame neorientovany graf
                Graph mapa = Graph.createFromFile("graf.txt");
                // Transformujeme vsetky hrany grafu na orientovane
                // mapa.setDirected(true);

                System.out.println(BellmanFord.bellmanFord(mapa, mapa.getVertex("A")));
                System.out.println(BellmanFord.cesta(mapa, mapa.getVertex("A"),
                                mapa.getVertex("G")));
        }

}