C9

import java.util.Arrays;
import java.util.Map;

import sk.upjs.paz.graph.Graph;
import sk.upjs.paz.graph.Vertex;


public class BellmanFord {

        static String[] labely;
        public static double[][] vytvorMaticuSusednosti(Graph g) {
        // Vyrobime pole vrcholov
        Vertex[] vrcholy = new Vertex[g.getVertices().size()];
        labely = new String[g.getVertices().size()];
        int idx = 0;
        for (Vertex v: g.getVertices()) {
                vrcholy[idx] = v;
                labely[idx] = v.getLabel();
                idx++;
        }

        // Vyrobime maticu susednosti;
        double[][] matica = 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])) {
                        matica[i][j] = g.getEdge(vrcholy[i], vrcholy[j]).getWeight();
                         } else {
                                matica[i][j] = Double.POSITIVE_INFINITY;
                         }

        return matica;
        }

        public static double[] bellmanFord(double[][] maticaSusednosti, String odkial) {
                double[] d = new double[maticaSusednosti.length];
                for (int i = 0; i < d.length; i++) {
                        if (labely[i].equals(odkial)) {
                                d[i] = 0;
                        } else {
                                d[i] = Double.POSITIVE_INFINITY;
                        }
                }

                for (int i = 0; i < maticaSusednosti.length; i++) {
                        //zrelaxujeme vsetky hrany
                        for (int u = 0; u < maticaSusednosti.length; u++) {
                                for (int v = 0; v < maticaSusednosti.length; v++) {
                                        if (maticaSusednosti[u][v] < Double.POSITIVE_INFINITY) {
                                                relax(u,v,d,maticaSusednosti);
                                        }
                                }
                        }
                }
                return d;
        }

        public static void relax(int u, int v, double[] d, double[][] maticaSusednosti) {
                if (d[v] > d[u] + maticaSusednosti[u][v]) {
                        d[v] = d[u] + maticaSusednosti[u][v];
                }
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf
        Graph fb = new Graph();
        // Nacitame zoznam hran zo suboru
        fb.setDirected(true);
        fb.loadFromFile("graf.txt");
        double[][] matica = vytvorMaticuSusednosti(fb);
        System.out.println(Arrays.toString(labely));
        for (int i = 0; i < matica.length; i++) {
                        System.out.println(Arrays.toString(matica[i]));
                }
        System.out.println(Arrays.toString(bellmanFord(matica, "A")));
        }

}
 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map;

import sk.upjs.paz.graph.Graph;
import sk.upjs.paz.graph.Vertex;


public class BellmanFord {

        static String[] labely;
        static int[] predchodca;

        public static double[][] vytvorMaticuSusednosti(Graph g) {
        // Vyrobime pole vrcholov
        Vertex[] vrcholy = new Vertex[g.getVertices().size()];
        labely = new String[g.getVertices().size()];
        int idx = 0;
        for (Vertex v: g.getVertices()) {
                vrcholy[idx] = v;
                labely[idx] = v.getLabel();
                idx++;
        }

        // Vyrobime maticu susednosti;
        double[][] matica = 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])) {
                        matica[i][j] = g.getEdge(vrcholy[i], vrcholy[j]).getWeight();
                         } else {
                                matica[i][j] = Double.POSITIVE_INFINITY;
                         }

        return matica;
        }

        public static double[] bellmanFord(double[][] maticaSusednosti, String odkial) {
                double[] d = new double[maticaSusednosti.length];
                for (int i = 0; i < d.length; i++) {
                        if (labely[i].equals(odkial)) {
                                d[i] = 0;
                        } else {
                                d[i] = Double.POSITIVE_INFINITY;
                        }
                }
                predchodca = new int[maticaSusednosti.length];
                for (int i = 0; i < predchodca.length; i++) {
                        predchodca[i] = -1;
                                }

                for (int i = 0; i < maticaSusednosti.length; i++) {
                        //zrelaxujeme vsetky hrany
                        for (int u = 0; u < maticaSusednosti.length; u++) {
                                for (int v = 0; v < maticaSusednosti.length; v++) {
                                        if (maticaSusednosti[u][v] < Double.POSITIVE_INFINITY) {
                                                relax(u,v,d,maticaSusednosti);
                                        }
                                }
                        }
                }
                return d;
        }

        public static ArrayList<Integer> cestaDo(int indexVrcholu){
                ArrayList<Integer> vrcholy = new ArrayList<Integer>();
                vrcholy.add(indexVrcholu);
                while (predchodca[indexVrcholu]!= -1) {
                                vrcholy.add(predchodca[indexVrcholu]);
                                indexVrcholu = predchodca[indexVrcholu];


                        }

                return vrcholy;
        }

        public static void relax(int u, int v, double[] d, double[][] maticaSusednosti) {
                if (d[v] > d[u] + maticaSusednosti[u][v]) {
                        d[v] = d[u] + maticaSusednosti[u][v];
                        predchodca[v] = u;
                }
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf
        Graph fb = new Graph();
        // Nacitame zoznam hran zo suboru
        fb.setDirected(true);
        fb.loadFromFile("Graf");
        double[][] matica = vytvorMaticuSusednosti(fb);
        System.out.println(Arrays.toString(labely));
        for (int i = 0; i < matica.length; i++) {
                        System.out.println(Arrays.toString(matica[i]));
                }
        System.out.println(Arrays.toString(bellmanFord(matica, "A")));
        System.out.println(cestaDo(3));
        }

}

        import java.util.ArrayList;
        import java.util.Arrays;
import java.util.HashSet;
        import java.util.Map;
import java.util.Set;

        import sk.upjs.paz.graph.Graph;
import sk.upjs.paz.graph.Vertex;


        public class Dijkstra {

                static String[] labely;
                static int[] predchodca;

                public static double[][] vytvorMaticuSusednosti(Graph g) {
                // Vyrobime pole vrcholov
                Vertex[] vrcholy = new Vertex[g.getVertices().size()];
                labely = new String[g.getVertices().size()];
                int idx = 0;
                for (Vertex v: g.getVertices()) {
                        vrcholy[idx] = v;
                        labely[idx] = v.getLabel();
                        idx++;
                }

                // Vyrobime maticu susednosti;
                double[][] matica = 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])) {
                                matica[i][j] = g.getEdge(vrcholy[i], vrcholy[j]).getWeight();
                                 } else {
                                        matica[i][j] = Double.POSITIVE_INFINITY;
                                 }

                return matica;
                }

                public static double[] dijkstra(double[][] maticaSusednosti, String odkial) {
                        double[] d = new double[maticaSusednosti.length];

                        for (int i = 0; i < d.length; i++) {
                                if (labely[i].equals(odkial)) {
                                        d[i] = 0;
                                } else {
                                        d[i] = Double.POSITIVE_INFINITY;
                                }
                        }
                        predchodca = new int[maticaSusednosti.length];
                        for (int i = 0; i < predchodca.length; i++) {
                                predchodca[i] = -1;
                                        }

                        Set<Integer> nevybavene = new HashSet<Integer>();
                        for (int i = 0; i < d.length; i++) {
                                nevybavene.add(i);

                                        }
                        while(!nevybavene.isEmpty()){
                                double najmensie = Double.POSITIVE_INFINITY;
                                int indexNajmensieho = -1;
                                for (Integer index : nevybavene) {
                                                        if(d[index] < najmensie){
                                                                najmensie = d[index];
                                                                indexNajmensieho = index;
                                                        }
                                                }
                                nevybavene.remove(indexNajmensieho);
                                for (int i = 0; i < d.length; i++) {
                                                    if(maticaSusednosti[indexNajmensieho][i] < Double.POSITIVE_INFINITY){
                                                        relax(indexNajmensieho, i, d, maticaSusednosti);
                                                    }
                                                }

                        }

                        return d;
                }

                public static ArrayList<Integer> cestaDo(int indexVrcholu){
                        ArrayList<Integer> vrcholy = new ArrayList<Integer>();
                        vrcholy.add(indexVrcholu);
                        while (predchodca[indexVrcholu]!= -1) {
                                        vrcholy.add(predchodca[indexVrcholu]);
                                        indexVrcholu = predchodca[indexVrcholu];


                                }

                        return vrcholy;
                }

                public static void relax(int u, int v, double[] d, double[][] maticaSusednosti) {
                        if (d[v] > d[u] + maticaSusednosti[u][v]) {
                                d[v] = d[u] + maticaSusednosti[u][v];
                                predchodca[v] = u;
                        }
                }

                /**
                 * @param args
                 */
                public static void main(String[] args) {
                        // Vytvorime graf
                Graph fb = new Graph();
                // Nacitame zoznam hran zo suboru
                fb.setDirected(true);
                fb.loadFromFile("Graf");
                double[][] matica = vytvorMaticuSusednosti(fb);
                System.out.println(Arrays.toString(labely));
                for (int i = 0; i < matica.length; i++) {
                                System.out.println(Arrays.toString(matica[i]));
                        }
                System.out.println(Arrays.toString(dijkstra(matica, "A")));
                System.out.println(cestaDo(3));
                }

        }
 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map;

import sk.upjs.paz.graph.Graph;
import sk.upjs.paz.graph.Vertex;


public class FloydWarshal {

        static String[] labely;
        static int[][] predchodca;

        public static double[][] vytvorMaticuSusednosti(Graph g) {
        // Vyrobime pole vrcholov
        Vertex[] vrcholy = new Vertex[g.getVertices().size()];
        labely = new String[g.getVertices().size()];
        int idx = 0;
        for (Vertex v: g.getVertices()) {
                vrcholy[idx] = v;
                labely[idx] = v.getLabel();
                idx++;
        }

        // Vyrobime maticu susednosti;
        double[][] matica = 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])) {
                        matica[i][j] = g.getEdge(vrcholy[i], vrcholy[j]).getWeight();
                         } else {
                                matica[i][j] = Double.POSITIVE_INFINITY;
                         }

        return matica;
        }

        public static double[][] floydWarshal(double[][] maticaSusednosti) {
                double[][] d = maticaSusednosti.clone();

                predchodca = new int[maticaSusednosti.length][maticaSusednosti.length];
                for (int i = 0; i < predchodca.length; i++) {
                        for (int j = 0; j < predchodca.length; j++) {
                                predchodca[i][j] = -1;
                        }
                                }

                                for (int k = 0; k < d.length; k++)
                                        for (int i = 0; i < d.length; i++)
                                                for (int j = 0; j < d.length; j++)
                                                        if (d[i][k] + d[k][j] < d[i][j]) {
                                                                d[i][j] = d[i][k] + d[k][j];
                                                                predchodca[i][j] = k;
                                                        }

                return d;
        }

        public static ArrayList<Integer> cesta(int i, int j, double[][] maticaSusednosti) {
                ArrayList<Integer> c = new ArrayList<Integer>();
                if (predchodca[i][j] == -1) {
                        if (maticaSusednosti[i][j] < Double.POSITIVE_INFINITY) {
                                c.add(i);c.add(j);
                                return c;
                        }
                        return null;
                }

                c = cesta(i, predchodca[i][j], maticaSusednosti);
                c.remove(c.size() - 1);
                c.addAll(cesta(predchodca[i][j], j, maticaSusednosti));
                return c;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf
        Graph fb = new Graph();
        // Nacitame zoznam hran zo suboru
        fb.setDirected(true);
        fb.loadFromFile("Graf");
        double[][] matica = vytvorMaticuSusednosti(fb);
        System.out.println(Arrays.toString(labely));
        for (int i = 0; i < matica.length; i++) {
                        System.out.println(Arrays.toString(matica[i]));
                }
        System.out.println(Arrays.toString(floydWarshal(matica)));
        System.out.println(cesta(0, 5, matica));
        }

}