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(""); } }

## Monday, May 14, 2012

### 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.

Subscribe to:
Posts (Atom)