Dijkstra Algorithm (Shortest Path Algorithm ) Java Code

Dijkstra Algorithm is used find the shortest path in a directed graphs. Following is a java implementation of the Dijkstra Algorithm.

class Dijkstra {

    public static void main(String[] args) {
        int length = 300;//length of the 2-D array
        int adjMatrix[][] = new int[length][length];
        CreateMatrix cm = new CreateMatrix();
        cm.createMatrix(length);
        adjMatrix = cm.readMatrix(adjMatrix);
        Dijkstra dk = new Dijkstra();
        dk.dijkstra(adjMatrix);

    }

    public void dijkstra(int adjMatrix[][]) {

        long startTime = System.nanoTime();
        int distance[] = new int[adjMatrix.length];
        int resolved[] = new int[adjMatrix.length];
        int prev[] = new int[adjMatrix.length];

        for (int i = 0; i < adjMatrix.length; i++) {
            distance[i] = Integer.MAX_VALUE;
            resolved[i] = Integer.MAX_VALUE;
            prev[i] = -1;
        }
        distance[ 0] = 0;
        resolved[ 0] = 0;

        int minNode = Integer.MAX_VALUE, position = 0;
        for (int i = 0; i < adjMatrix.length; i++) {
            for (int j = 0; j < resolved.length; j++) {
                if (minNode > distance[j] && resolved[j] != -1) {
                    minNode = distance[j];
                    position = j;
                }
            }
            resolved[position] = -1;

            for (int j = 0; j < adjMatrix.length; j++) {
                if (distance[j] > adjMatrix[position][j] + distance[position]) {
                    distance[j] = adjMatrix[position][j] + distance[position];
                    prev[j] = position;
                }
            }
            minNode = Integer.MAX_VALUE;
		}
        long runTime = System.nanoTime() - startTime;
        System.out.println("Runtime =" + runTime + " nano seconds");
        System.out.println("Distance Array");
        for (int j = 0; j < distance.length; j++) {
            System.out.print(" " + distance[j]);
        }
        System.out.println("");
        System.out.println("Predecessor Array");
        for (int i = 0; i < prev.length; i++) {
            System.out.print(" " + prev[i]);
        }
        System.out.println("");
    }
}