A9

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

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

public class Dijkstra {

        // Vytvori ku neohodnotenemu grafu prisluchajucu maticu susednosti
        public static double[][] grafNaMaticuSusednosti(Graph g) {
                Vertex[] vrcholyVPoli = g.createVertexArray();
                System.out.println(Arrays.toString(vrcholyVPoli));
                double[][] matica = g.createWeightedAdjacencyMatrix(vrcholyVPoli);
                return matica;
        }

        public static void dijkstra(double[][] oms, int start, double[] d, int[] predchodca) {
                Arrays.fill(d, Double.POSITIVE_INFINITY);
                d[start] = 0;

                Arrays.fill(predchodca, -1);

                boolean[] q = new boolean[d.length];
                Arrays.fill(q, true);

                while (true) {
                        // Najdeme vrchol z q, ktory ma najmensie d-cko
                        int kandidat = -1;
                        double dKandidata = Double.POSITIVE_INFINITY;
                        for (int i = 0; i < d.length; i++)
                                if (q[i] && d[i] < dKandidata) {
                                        kandidat = i;
                                        dKandidata = d[i];
                                }

                        // Overime, ci nie je "ze uz koniec"
                        if (kandidat == -1) {
                                break;
                        }

                        q[kandidat] = false;

                        for (int i = 0; i < d.length; i++) {
                                if (oms[kandidat][i] != Double.POSITIVE_INFINITY) {
                                        // nasli sme orientovanu hranu (kandidat, i) a ideme ju
                                        // relaxovat
                                        if (d[kandidat] + oms[kandidat][i] < d[i]) {
                                                d[i] = d[kandidat] + oms[kandidat][i];
                                                predchodca[i] = kandidat;
                                        }
                                }
                        }
                }
        }

        public static List<Integer> cesta(int kam, int[] predchodca) {
                List<Integer> vysledok = new ArrayList<Integer>();
                vysledok.add(kam);
                while (predchodca[kam] != -1) {
                        vysledok.add(predchodca[kam]);
                        kam = predchodca[kam];
                }

                Collections.reverse(vysledok);
                return vysledok;
        }

        public static void main(String[] args) {
                Graph g = Graph.createFromFile("ograf.txt");
                double[][] oms = grafNaMaticuSusednosti(g);
                Scanner citac = new Scanner(System.in);
                int startIdx = citac.nextInt();

                double[] d = new double[oms.length];
                int[] predchodca = new int[oms.length];

                dijkstra(oms, startIdx, d, predchodca);
                System.out.println(Arrays.toString(d));
                System.out.println(Arrays.toString(predchodca));
        }

}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

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

public class DijkstraCezMaticu {

        // Vytvori ku neohodnotenemu grafu prisluchajucu maticu susednosti
        public static double[][] grafNaMaticuSusednosti(Graph g) {
                Vertex[] vrcholyVPoli = g.createVertexArray();
                System.out.println(Arrays.toString(vrcholyVPoli));
                double[][] matica = g.createWeightedAdjacencyMatrix(vrcholyVPoli);
                return matica;
        }

        public static List<Integer> dikstra(int odkial, int kam, double[][] oms) {
                double[] d = new double[oms.length];
                Arrays.fill(d, Double.POSITIVE_INFINITY);
                d[odkial] = 0;

                boolean[] q = new boolean[d.length];
                Arrays.fill(q, true);
                int pocetNevybavenych = d.length;

                int[] p = new int[d.length];
                Arrays.fill(p, -1);

                while (pocetNevybavenych > 0) {

                        // Najdeme vrchol v ako vrchol s najmensim odhadom z Q
                        int v = -1;
                        for (int i = 0; i < d.length; i++)
                                if (q[i] && ((v == -1) || (d[i] < d[v]))) {
                                        v = i;
                                }

                        if (d[v] == Double.POSITIVE_INFINITY) {
                                break;
                        }

                        // Vyhodime v z Q
                        q[v] = false;
                        pocetNevybavenych--;

                        // Relaxujeme hrany z vrcholu v
                        for (int i = 0; i < d.length; i++)
                                if (oms[v][i] != Double.POSITIVE_INFINITY) {
                                        // Ak som tu, mame hranu z v do i a zrelaxujeme ju

                                        // Relax
                                        if (d[v] + oms[v][i] < d[i]) {
                                                d[i] = d[v] + oms[v][i];
                                                p[i] = v;
                                        }
                                }
                }

                //System.out.println(Arrays.toString(d));

                // Ak odhad ciela je nekonecno, nevieme sa tam dostat
                if (d[kam] == Double.POSITIVE_INFINITY) {
                        return null;
                }

                // Vybudujeme cestu cuvanim
                List<Integer> cesta = new ArrayList<Integer>();
                cesta.add(kam);
                int kdeSom = kam;
                while (kdeSom != odkial) {
                        cesta.add(p[kdeSom]);
                        kdeSom = p[kdeSom];
                }
                Collections.reverse(cesta);
                return cesta;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                Graph g = Graph.createFromFile("oog.txt");
                double[][] maticaSusednosti = grafNaMaticuSusednosti(g);
                Scanner citac = new Scanner(System.in);
                System.out.println("Zadaj odkial:");
                int odkial = citac.nextInt();
                System.out.println("Zadaj kam:");
                int kam = citac.nextInt();

                dikstra(odkial, kam, maticaSusednosti);
        }

}