A9

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

public class Grafy {

        // Relaxacia orientovanej hrany
        public static void relax(Edge e, Map<Vertex, Double> d) {
                Vertex u = e.getSource();
                Vertex v = e.getTarget();
                if (d.get(u) + e.getWeight() < d.get(v))
                        d.put(v, d.get(u) + e.getWeight());
        }

        // Bellman-Fordov algoritmus
        public static Map<Vertex, Double> bellmanFord(Graph g, Vertex s) {
                // Iba orientovane grafy su akceptovane ako vstup
                if (!g.isDirected())
                        throw new RuntimeException(
                                        "Len orientovane grafy su akceptovane pre Bellman-Fordov algoritmus");

                // Vytvorime map, v ktorom budeme pre kazdy vrchol udrziavat aktualny
                // horny odhad dlzky najkratsej cesty z s do tohto vrcholu
                Map<Vertex, Double> d = new HashMap<Vertex, Double>();

                // Inicializacia predbeznych najkratsich vzdialenosti
                for (Vertex v : g.getVertices())
                        d.put(v, Double.POSITIVE_INFINITY);
                d.put(s, 0d);

                // n-krat opakujeme relaxaciu vsetkych hran
                for (int i = 0; i < g.getVertices().size(); i++)
                        for (Edge e : g.getEdges())
                                relax(e, d);

                return d;
        }

        public static List<Vertex> cestaDo(Vertex odkial, Vertex kam, Map<Vertex, Double> d) {
                List<Vertex> cesta = new ArrayList<Vertex>();

                Vertex aktualny = kam;
                while (aktualny != odkial) {
                        cesta.add(aktualny);
                        for (Edge h : aktualny.getInEdges())
                                if (d.get(h.getSource()) + h.getWeight() == d.get(aktualny)) {
                                        aktualny = h.getSource();
                                        break;
                                }
                }
                cesta.add(aktualny);
                Collections.reverse(cesta);

                return cesta;
        }

        public static void main(String[] args) {
                Graph mapa = new Graph();
                mapa.loadFromFile("graf.txt");
                mapa.setDirected(true);
                Map<Vertex, Double> d = bellmanFord(mapa, mapa.getVertex("A"));
                System.out.println(d);
                System.out.println(cestaDo(mapa.getVertex("G"), d));
        }
}

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

public class Grafy {

        // Relaxacia orientovanej hrany
        public static void relax(Edge e, Map<Vertex, Double> d,
                        Map<Vertex, Vertex> predchodca) {
                Vertex u = e.getSource();
                Vertex v = e.getTarget();
                if (d.get(u) + e.getWeight() < d.get(v)) {
                        d.put(v, d.get(u) + e.getWeight());
                        predchodca.put(v, u);
                }
        }

        // Bellman-Fordov algoritmus
        public static Map<Vertex, Double> bellmanFord(Graph g, Vertex s,
                        Map<Vertex, Vertex> predchodca) {
                // Iba orientovane grafy su akceptovane ako vstup
                if (!g.isDirected())
                        throw new RuntimeException(
                                        "Len orientovane grafy su akceptovane pre Bellman-Fordov algoritmus");

                predchodca.clear();

                // Vytvorime map, v ktorom budeme pre kazdy vrchol udrziavat aktualny
                // horny odhad dlzky najkratsej cesty z s do tohto vrcholu
                Map<Vertex, Double> d = new HashMap<Vertex, Double>();

                // Inicializacia predbeznych najkratsich vzdialenosti
                for (Vertex v : g.getVertices())
                        d.put(v, Double.POSITIVE_INFINITY);
                d.put(s, 0d);

                // n-krat opakujeme relaxaciu vsetkych hran
                for (int i = 0; i < g.getVertices().size(); i++)
                        for (Edge e : g.getEdges())
                                relax(e, d, predchodca);

                return d;
        }

        public static List<Vertex> cestaDo(Vertex odkial, Vertex kam,
                        Map<Vertex, Double> d) {
                List<Vertex> cesta = new ArrayList<Vertex>();

                Vertex aktualny = kam;
                while (aktualny != odkial) {
                        cesta.add(aktualny);
                        for (Edge h : aktualny.getInEdges())
                                if (d.get(h.getSource()) + h.getWeight() == d.get(aktualny)) {
                                        aktualny = h.getSource();
                                        break;
                                }
                }
                cesta.add(aktualny);
                Collections.reverse(cesta);

                return cesta;
        }

        public static List<Vertex> cestaDo2(Vertex odkial, Vertex kam,
                        Map<Vertex, Vertex> predchodca) {
                List<Vertex> cesta = new ArrayList<Vertex>();

                Vertex aktualny = kam;
                while (aktualny != odkial) {
                        cesta.add(aktualny);
                        aktualny = predchodca.get(aktualny);

                }
                cesta.add(aktualny);
                Collections.reverse(cesta);

                return cesta;
        }

        public static double[][] grafNaMaticu(Graph g) {
                // Vyrobime pole vrcholov
                Vertex[] vrcholy = new Vertex[g.getVertices().size()];
                int idx = 0;
                for (Vertex v : g.getVertices()) {
                        vrcholy[idx] = v;
                        idx++;
                }
                System.out.println(Arrays.toString(vrcholy));
                // Vyrobime pole, do ktoreho budeme davat vzajomne vzdialenosti
                double[][] d = new double[vrcholy.length][vrcholy.length];
                for (int i = 0; i < vrcholy.length; i++)
                        for (int j = 0; j < vrcholy.length; j++)
                                if (g.hasEdge(vrcholy[i], vrcholy[j]))
                                        d[i][j] = g.getEdge(vrcholy[i], vrcholy[j]).getWeight();
                                else
                                        d[i][j] = Double.POSITIVE_INFINITY;

                return d;
        }

        // Dijkstrov algoritmus
        public static double[] dijkstra(double[][] g, int startIdx) {
                double[] d = new double[g.length];

                Arrays.fill(d, Double.POSITIVE_INFINITY);
                d[startIdx] = 0;
                boolean[] nevybavene = new boolean[g.length];
                Arrays.fill(nevybavene, true);
                int pocetNevybavenych = g.length;
                while (pocetNevybavenych > 0) {
                        // Vyberieme vrchol, ktory spomedzi nevybavenych ma najmensi
                        // medzivysledok d
                        double min = Double.MAX_VALUE;
                        int idx = -1;
                        for (int i = 0; i < d.length; i++) {
                                if (nevybavene[i]) {
                                        if (d[i] < min) {
                                                min = d[i];
                                                idx = i;
                                        }
                                }
                        }

                        // Nechame zrelaxovat vsetky z neho vychadzajuce hrany
                        for (int j = 0; j < g.length; j++)
                                if (d[idx] + g[idx][j] < d[j])
                                        d[j] = d[idx] + g[idx][j];

                        // Vybrany vrchol vyberieme z mnoziny nevybavenych
                        nevybavene[idx] = false;
                        pocetNevybavenych--;
                }

                return d;
        }

        public static void main(String[] args) {
                Graph mapa = new Graph();
                mapa.loadFromFile("graf.txt");
                mapa.setDirected(true);
                Map<Vertex, Vertex> predchodca = new HashMap<Vertex, Vertex>();
                Map<Vertex, Double> d = bellmanFord(mapa, mapa.getVertex("A"),
                                predchodca);
                System.out.println(d);
                System.out
                                .println(cestaDo(mapa.getVertex("A"), mapa.getVertex("G"), d));
                System.out.println(cestaDo2(mapa.getVertex("A"), mapa.getVertex("G"),
                                predchodca));
                double [][] matica = grafNaMaticu(mapa);
                System.out.println(Arrays.toString(dijkstra(matica, 0)));
        }
}