B10

package sk.upjs.paz.cvicenie10;

public class NajkratsieCesty {

    private static int[] bellmanFord(int[][] matica, int start) {
        return null;
    }

    private static int[] dijkstra(int[][] matica, int start) {
        return null;
    }

    private static int[][] floydWarshall(int[][] matica) {
        return null;
    }

    public static void main(String[] args) {
        // nekonecno
        int x = -1;
        int[][] matica = {
                {0, 2, x, 9, x, 1},
                {2, 0, 3, x, 8, x},
                {x, 3, 0, 4, x, 7},
                {9, x, 4, 0, 5, x},
                {x, 8, x, 5, 0, 6},
                {1, x, 7, x, 6, 0}
        };

    }
}
 

package sk.upjs.paz.cvicenie10;

import java.util.Arrays;

public class NajkratsieCesty {

    public static final int INF = Integer.MAX_VALUE / 2;

    private static int[] bellmanFord(int[][] matica, int start) {
        return null;
    }

    private static int[] dijkstra(int[][] matica, int start) {
        int[] d = new int[matica.length];
        Arrays.fill(d, INF);
        d[start] = 0;
        // mnozina Q obsahuje vsetky vrcholy
        boolean[] q = new boolean[matica.length];
        Arrays.fill(q, true);
        for (int j = 0; j < matica.length; j++) {
            int index = -1;
            int dist = Integer.MAX_VALUE;
            for (int i = 0; i < matica.length; i++) {
                if (q[i] && d[i] < dist) {
                    index = i;
                    dist = d[i];
                }
            }
            // relax
            for (int i = 0; i < matica.length; i++) {
                if (matica[index][i] != INF && index != i) {
                    if (d[index] + matica[index][i] < d[i])
                        d[i] = d[index] + matica[index][i];
                }
            }

            q[index] = false;
        }

        return d;
    }

    private static int[][] floydWarshallK(int[][] matica) {
        /*int[][] d = new int[matica.length][matica[0].length];
        for (int i = 0; i < d.length; i++) {
            Arrays.fill(d[i], INF);
        }*/
        int[][] d = matica.clone();
        int n = matica.length;


        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)

                  /*  if (d[i][k] != INF && d[k][j] != INF)
                        if (d[i][j] == INF || d[i][k] + d[k][j] < d[i][j])
                            d[i][j] = d[i][k] + d[k][j];*/
                    if (d[i][k] + d[k][j] < d[i][j])
                        d[i][j] = d[i][k] + d[k][j];
        return d;
    }

    private static int[][] floydWarshall(int[][] matica) {
        /*int[][] d = new int[matica.length][matica[0].length];
        for (int i = 0; i < d.length; i++) {
            Arrays.fill(d[i], INF);
        }*/
        int[][] d = matica.clone();
        int n = matica.length;

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                   /* if (d[i][k] != INF && d[k][j] != INF)
                        if (d[i][j] == INF || d[i][k] + d[k][j] < d[i][j])
                            d[i][j] = d[i][k] + d[k][j];*/
                    if (d[i][k] + d[k][j] < d[i][j])
                        d[i][j] = d[i][k] + d[k][j];

        return d;
    }

    public static void main(String[] args) {
        // nekonecno
        int x = INF;
        /*int[][] matica = {
                {0, 2, x, 9, x, 1},
                {2, 0, 3, x, 8, x},
                {x, 3, 0, 4, x, 7},
                {9, x, 4, 0, 5, x},
                {x, 8, x, 5, 0, 6},
                {1, x, 7, x, 6, 0}
        };*/
        int[][] matica = new int[5][5];
        for (int i = 0; i < matica.length; i++) {
            for (int j = 0; j < matica[0].length; j++) {
                matica[i][j] = INF;
            }
        }
        for (int i = 0; i < matica.length; i++) {
            matica[i][i] = 0;
        }
        /*for (int i = 0; i < 100; i++) {
            int index1 = (int) (Math.random() * 100);
            int index2 = (int) (Math.random() * 100);
            int value = (int) (Math.random() * 1000) + 1;
            if (index1 != index2) {
                matica[index1][index2] = matica[index2][index1] = value;
            }
        }*/
        matica[0][1] = matica[1][0] = 10;
        matica[1][2] = matica[2][1] = 13;
        matica[2][3] = matica[3][2] = 1;
        matica[3][4] = matica[4][3] = 2;
        matica[4][0] = matica[0][4] = 3;
        System.out.println(Arrays.deepToString(matica));
        int[][] res1 = floydWarshall(matica);
        int[][] res2 = floydWarshallK(matica);
        System.out.println(Arrays.deepToString(res1));
        System.out.println(Arrays.deepToString(res2));
        System.out.println(Arrays.deepEquals(res1, res2));

    }
}