D9

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

public class GrafoveAlg {

        static double n = Double.POSITIVE_INFINITY;

        static double[][] matica = new double[][] { { n, 4, n, 9, n, n },
                        { n, n, 7, n, 3, n }, { n, n, n, 8, n, n }, { n, n, n, n, 2, n },
                        { n, n, n, n, n, 10 }, { n, n, n, n, n, n } };

        public static void floydovAlg() {
                for (int k = 0; k < matica.length; k++) {
                        for (int i = 0; i < matica.length; i++) {
                                for (int j = 0; j < matica.length; j++) {
                                        if (matica[i][k] + matica[k][j] < matica[i][j])
                                                matica[i][j] = matica[i][k] + matica[k][j];
                                }
                        }
                }
        }

        public static void BellAlg() {
                double[] d = new double[matica.length];
                double[] cesta = new double[matica.length];
                int start = 0;
                for (int i = 0; i < d.length; i++) {
                        d[i] = Double.POSITIVE_INFINITY;
                        cesta[i] = Double.POSITIVE_INFINITY;
                }
                d[start] = 0;
                for (int k = 0; k < matica.length; k++) {
                        for (int i = 0; i < matica.length; i++) {
                                for (int j = 0; j < matica.length; j++) {
                                        if (matica[i][j] != Double.POSITIVE_INFINITY) {
                                                if (d[k] + matica[k][j] < d[j]){
                                                        d[j] = d[k] + matica[k][j];
                                                        cesta[j] = k;
                                                }
                                        }
                                }
                        }
                }

                System.out.println(Arrays.toString(d));
                System.out.println(Arrays.toString(cesta));
        }


        public static void DijksAlg(){
                double[] d = new double[matica.length];
                int start = 0;
                for (int i = 0; i < d.length; i++) {
                        d[i] = Double.POSITIVE_INFINITY;
                }
                d[start] = 0;

                Set<Integer> vrcholy = new HashSet<Integer>();
                for (int i = 0; i < d.length; i++) {
                        vrcholy.add(i);
                }
                double min = Double.MAX_VALUE;
                double index = -1;
                while(!vrcholy.isEmpty()){
                        for (Integer v : vrcholy) {
                                System.out.println(v);
                                if(min>d[v]){
                                        min = d[v];
                                        index = v;
                                }
                        for (int j = 0; j < matica.length; j++) {
                                if(matica[(int) index][j]!=Double.POSITIVE_INFINITY){
                                        if (d[(int)index] + matica[(int)index][j] < d[j]){
                                                d[j] = d[(int)index] + matica[(int)index][j];
                                        }
                                }
                        }
                        vrcholy.remove(v);
                        }
                }
                System.out.println(Arrays.toString(d));
        }

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

                DijksAlg();
                // System.out.println(Arrays.deepToString(matica));
//              for (int i = 0; i < matica.length; i++) {
//                      System.out.println(Arrays.toString(matica[i]));
//              }



        }

}
 

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

public class GrafoveAlg {

        static double n = Double.POSITIVE_INFINITY;

        static double[][] matica = new double[][] { { n, 4, n, 9, n, n },
                        { n, n, 7, n, 3, n }, { n, n, n, 8, n, n }, { n, n, n, n, 2, n },
                        { n, n, n, n, n, 10 }, { n, n, n, n, n, n } };

        public static void floydovAlg() {
                for (int k = 0; k < matica.length; k++) {
                        for (int i = 0; i < matica.length; i++) {
                                for (int j = 0; j < matica.length; j++) {
                                        if (matica[i][k] + matica[k][j] < matica[i][j])
                                                matica[i][j] = matica[i][k] + matica[k][j];
                                }
                        }
                }
        }

        public static void BellAlg() {
                double[] d = new double[matica.length];
                double[] cesta = new double[matica.length];
                int start = 0;
                for (int i = 0; i < d.length; i++) {
                        d[i] = Double.POSITIVE_INFINITY;
                        cesta[i] = Double.POSITIVE_INFINITY;
                }
                d[start] = 0;
                for (int k = 0; k < matica.length; k++) {
                        for (int i = 0; i < matica.length; i++) {
                                for (int j = 0; j < matica.length; j++) {
                                        if (matica[i][j] != Double.POSITIVE_INFINITY) {
                                                if (d[k] + matica[k][j] < d[j]) {
                                                        d[j] = d[k] + matica[k][j];
                                                        cesta[j] = k;
                                                }
                                        }
                                }
                        }
                }

                System.out.println(Arrays.toString(d));
                System.out.println(Arrays.toString(cesta));
        }

        public static void DijksAlg() {
                double[] d = new double[matica.length];
                int start = 0;
                for (int i = 0; i < d.length; i++) {
                        d[i] = Double.POSITIVE_INFINITY;
                }
                d[start] = 0;

                Set<Integer> vrcholy = new HashSet<Integer>();

                for (int i = 0; i < d.length; i++) {
                        vrcholy.add(i);
                }
                double min = Double.MAX_VALUE;
                double index = -1;
                while (!vrcholy.isEmpty()) {

                        for (Iterator<Integer> it = vrcholy.iterator(); it.hasNext();) {
                                Integer i = it.next();

                                System.out.println(i);

                                if (min > d[i]) {
                                        min = d[i];
                                        index = i;
                                }
                                for (int j = 0; j < matica.length; j++) {
                                        if (matica[(int) index][j] != Double.POSITIVE_INFINITY) {
                                                if (d[(int) index] + matica[(int) index][j] < d[j]) {
                                                        d[j] = d[(int) index] + matica[(int) index][j];
                                                }
                                        }
                                }
                                it.remove();
                        }
                }
                System.out.println(Arrays.toString(d));
        }

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

                System.out.println(Arrays.deepToString(matica));
                for (int i = 0; i < matica.length; i++) {
                        System.out.println(Arrays.toString(matica[i]));
                }

                BellAlg();
                DijksAlg();

        }

}