Dijkstra.java

import java.util.Arrays;

class Dijkstra {

    private final static double INF = Double.POSITIVE_INFINITY;

    // Time complexity: O(n²)
    public static void dijkstra(double[][] C, double[] D, int[] pred, int s) {

        int n = D.length;

        boolean[] V = new boolean[n];

        V[s] = true;
        C[s][s] = 0;

        for (int i = 0; i < n; i++) {
            D[i] = C[s][i];
            pred[i] = s;
        }

        for (int i = 0; i < n - 1; i++) {

            int h = min(D, V);

            V[h] = true;
            for (int k = 0; k < n; k++) {
                if (!V[k] && D[h] + C[h][k] < D[k]) {
                    pred[k] = h;
                    D[k] = D[h] + C[h][k];
                }
            }
        }

    }


    private static int min(double[] D, boolean[] V) {
        int k = 0, h = -1, n = D.length;

        for (; h == -1 && k < n; k++)
            if (!V[k] && D[k] != INF)
                h = k;

        for (; k < n; k++)
            if (!V[k] && D[k] != INF && D[k] < D[h])
                h = k;

        return h;
    }


    public static void main(String[] args) {

        int n = 6;
        double[][] C = new double[n][n];

        for (double[] array : C)
            for (int i = 0; i < n; i++)
                array[i] = INF;

        C[0][1] = 57;
        C[0][2] = 12;
        C[2][1] = 2;
        C[1][3] = 24;
        C[1][5] = 45;
        C[2][4] = 6;
        C[4][3] = 31;

        double[] D = new double[n];
        int[] pred = new int[n];

        int s = 0;

        dijkstra(C, D, pred, s);

        System.out.println(Arrays.toString(D));
        System.out.println(Arrays.toString(pred));
    }

}