CC-20 : Implement Dijkstra’s shortest path algorithm.

Description:

Dijkstra’s shortest path algorithm helps to find path with shortest distance from a given source vertex to all other vertices in the graph. Given a matrix which contains the distances between vertices, Implement Dijkstra’s algorithm and execute it for input graph.

Test cases and expected outputs:

Input Parameters	Expected outputs
Input graph matrix indicating distances between vertices : 0,4,6,8, 0,0,1,2, 0,0,0,1, 0,0,0,0,	Shortest distances from 0 to rest of vertices: Distance from 0 to 0 is 0 Distance from 0 to 1 is 4 Distance from 0 to 2 is 5 Distance from 0 to 3 is 6

Pseudocode:

Dijkstra(int vertices,int[][] matrix, int src) method:

Initialize integer array named visited, to hold information whether the vertices have been visited.

Initialize integer array named distances , to hold distances from src node to other nodes.

Iterate through vertices using a for loop with iIdx as loop variable and iterate with value of iIdx from 0 to vertices count-1:

Set visited[iIdx]=0.

Set dist[Idx] to Integer.MaxValue.

Set dist[src]=0.

Iterate through vertices using a for loop with iIdx as loop variable and iterate with value of iIdx from 0 to vertices count-1:

Set in variable vertex1 to return value from findMinDistance(dist, visited).

Set visited[vertex1]=1.

Iterate through vertices using a for loop with vertex2 as loop variable and iterate with value of vertex2 from 0 to vertices count-1:

If vertex2 is not visited and distance from vertex1 to vertex2 is not 0 and sum of distances from src to vertex1 and distance from vertex1 to vertex2 is lesser than distance from src to vertex2 then:

Set dist[vertext2]= sum of distances from src to vertex1 and distance from vertex1 to vertex2.

Using a for loop iterate through dist array and print out the distance from src to other vertices.

findMinDistance(int[] dist, int[] visited) method:

Initialize int variable minDist to Integer.MaxValue.

Initialize int variable minDistVertex to -1.

Iterate through input dist[] array using a for loop with iIdx as loop variable and iterate with value of iIdx from 0 to dist.length:

If visited[iIdx] and dist[iIdx] < minDist:

Set minDist[iIdx]=dist[iIdx].

minDistanceVertex=iIdx.

return minDistanceVertex.

Code:

public void dijkstra(int vertices, int[][] matrix, int src){
	int[] visited=new int[vertices];
	int [] dist=new int[vertices];
	for(int iIdx=0; iIdx < vertices;iIdx++) {
		visited[iIdx]=0;
		dist[iIdx]=Integer.MAX_VALUE;
	}
	dist[src]=0;
	for(int iIdx=0; iIdx < vertices;iIdx++) {
		int vertex1=findMinDist(dist,visited);
		visited[vertex1]=1;
		for(int vertex2=0; vertex2 < vertices;vertex2++) {
			if ((visited[vertex2]==0) && (matrix[vertex1][vertex2] !=0)
			&& (dist[vertex1]+matrix[vertex1][vertex2] < dist[vertex2])) {
				dist[vertex2]=dist[vertex1]+matrix[vertex1][vertex2];
			}
		}
	}
	for(int iIdx=0; iIdx < vertices;iIdx++) {
		System.out.println("Distance from "+src+ " to "+ iIdx + " is "+dist[iIdx]);
	}	
} 

private int findMinDist(int[] dist, int[] visited) {
	int minDist=Integer.MAX_VALUE;
	int minDistVertex=-1;
	for(int iIdx=0; iIdx < dist.length;iIdx++) {
		if ((visited[iIdx]==0) && (dist[iIdx] < minDist)) {
			minDist=dist[iIdx];
			minDistVertex=iIdx;
		}
	}
	return minDistVertex;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class GraphDijkstra {

public void dijkstra(int vertices, int[][] matrix, int src){
	int[] visited=new int[vertices];
	int [] dist=new int[vertices];
	for(int iIdx=0; iIdx < vertices;iIdx++) {
		visited[iIdx]=0;
		dist[iIdx]=Integer.MAX_VALUE;
	}
	dist[src]=0;
	for(int iIdx=0; iIdx < vertices;iIdx++) {
		int vertex1=findMinDist(dist,visited);
		visited[vertex1]=1;
		for(int vertex2=0; vertex2 < vertices;vertex2++) {
			if ((visited[vertex2]==0) && (matrix[vertex1][vertex2] !=0)
			&& (dist[vertex1]+matrix[vertex1][vertex2] < dist[vertex2])) {
				dist[vertex2]=dist[vertex1]+matrix[vertex1][vertex2];
			}
		}
	}
	for(int iIdx=0; iIdx < vertices;iIdx++) {
		System.out.println("Distance from "+src+ " to "+ iIdx + " is "+dist[iIdx]);
	}	
} 

private int findMinDist(int[] dist, int[] visited) {
	int minDist=Integer.MAX_VALUE;
	int minDistVertex=-1;
	for(int iIdx=0; iIdx < dist.length;iIdx++) {
		if ((visited[iIdx]==0) && (dist[iIdx] < minDist)) {
			minDist=dist[iIdx];
			minDistVertex=iIdx;
		}
	}
	return minDistVertex;
}

public static void print2dArray(int[][] intArray, String label) throws Exception {
	// Case 1: The input Array is null !!
    if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
    // Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	System.out.println();
	System.out.println("************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

public static void main(String[] args) {

	int[][] retVal;
	try {
	GraphDijkstra gph=new GraphDijkstra();
	int[][] matrix = {	{0,4,6,8},
						{0,0,1,2},	
						{0,0,0,1},
						{0,0,0,0}};
	print2dArray(matrix, " Matrix" );
	gph.dijkstra(4, matrix, 0);
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}



}