In this tutorial, we will learn about the Dijkstra algorithm and we will also see the program to implement the Dijkstra algorithm using Java.
So before proceeding towards the code, Let us first understand the Dijkstra algorithm. Dijkstra algorithm solves the single-source shortest path problem. However, the algorithm works only on a directed and positively weighted graph. Positively weighted graph means where weights of all edges are non-negative i.e G=(V, E) is a positively weighted graph then w( u, v) ≥ 0. Dijkstra's algorithm is a greedy algorithm.
For a given graph G=(V, E) and a source vertex s, it maintains a set S of vertices. Initially, no vertex is in S. For a vertex u ϵ V - S, (i.e for a vertex which is in V but is not in S) if it has the minimum shortest distance from source s to u then u is added to S. This process is continued till V - S is not equal to null.
Please note that here in the code visited[] array does the work of set S i.e it keeps track of the vertices that have been visited and we also ask for the destination to print the shortest path between source and destination.
This is the graph that we have taken as an example for the code given below
import java.util.Scanner; public class Dijkstra { public static int V ; //this function is used to find the minimum distance of a node from the source which is not visited yet public int Find_min_dist(int distance[], boolean[] visited) { int min = 9999, index = -1; for (int v = 0; v < V; v++) if (visited[v] == false && distance[v] <= min) { min = distance[v]; index = v; } return index; } //Here the distance is printed from the source vertex to each vertex in the graph public void printSolution(int distance[]) { System.out.println("Vertex \t\t Distance from Source"); for (int i = 0; i < V; i++) System.out.println(+(i+1) + " \t\t " + distance[i]); } Dijkstra(int adj[][], int src,int end) { int distance[] = new int[V]; boolean visited[] = new boolean[V]; for (int i = 0; i < V; i++) { distance[i] = 9999; visited[i] = false; } distance[src] = 0; for (int i = 0; i < V - 1; i++) { int u = Find_min_dist(distance, visited); visited[u] = true; //if previous minimum distance from src to v is greater than distance[u] + adj[u][v] then distance[v] is updated for (int v = 0; v < V; v++) if (visited[v]==false && adj[u][v] != 0 && distance[u] != 9999 && distance[u] + adj[u][v] < distance[v]) distance[v] = distance[u] + adj[u][v]; } printSolution(distance); findpath(distance,adj,end,src); } // findpath() is used to print the shortest path from source to the destination public void findpath(int distance[], int adj[][],int destination,int src) { int path[]=new int[V]; //path[] is used as a queue in which all the nodes which are a part of the shortest path are inserted boolean visited[] = new boolean[V]; int index=-1,i=0,min=9999,j,count=0; path[0]=destination; //here declaring visited[i] for all vertices as false to backtrack from destination to src to get the shortest path for(i=0;i<V;i++) visited[i]=false; for(i=0;i<V;i++) { min=9999; for( j=0;j<V;j++) {// Here backtrack from destination to src and adding all the nodes to path[] which are a part of the shortest path if(adj[destination][j]!=0&&visited[j]==false&&adj[destination][j]+distance[j]<min) { index=j; min=adj[destination][j]+distance[j]; visited[j]=true; } } path[i+1]=index; destination=index; count++; if(destination==src) break; } System.out.println("The path from Source to Destination is:"); for(i=count;i>0;i--) { System.out.print(path[i]+1); System.out.print("-->"); } System.out.print(path[i]+1); } public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.print("Enter the total no. of vertices:"); V=sc.nextInt(); int adj[][] = new int[V][V]; //Asking the user for the adjacency matrix System.out.println("Enter the adjacency matrix for "+V+" vertices"); for(int i=0;i<V;i++) { for(int j=0;j<V;j++) { System.out.print("Enter Adj["+(i+1)+"]["+(j+1)+"]:"); adj[i][j]=sc.nextInt(); } } System.out.println("Enter the Source node:"); int src=sc.nextInt()-1; System.out.println("Enter the Destination node:"); int end=sc.nextInt()-1; Dijkstra obj = new Dijkstra(adj, src,end); sc.close(); } }
Output:
1) 2)
Submitted by Abhishek Birendra Verma (AbhishekVerma)
Download packets of source code on Coders Packet
Comments