Today, I introduce you to Dijkstra’s Shortest Path Algorithm in Java, both concept and implementation. Dijkstra’s algorithm is one of the common algorithms and here is implemented with a graph in the adjacent matrix.
Dijkstra’s Shortest Path Algorithm in Java
What’s Dijkstra’s algorithm?
Dijkstra’s algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph. It’s also very similiar to Prim’s algorithm for minimum spanning tree.
What is Shortest Path?
In general, the shortest path problem is about finding a path between 2 vertices in a graph such that the total sum of the edges weights is minimum.
How Dijkstra’s algorithm works
The Dijkstra’s algorithm works on any subpath from a vertex to another vertex, and let’s evaluate the distance of each vertex from the starting vertex. Then we visit from the starting vertex and its adjacencies to find subpath to those adjacencies.
Now, we consider a graph with four vertices like a example, see the below image.
Step 1: Choose the starting vertex is 10, then go to each the adjacent vertex and update its the minimum weight. Here there is two adjacent vertices are 20 and 40 and those weights are 3 and 1, then update weight 1 in short path.
Step 2: If the shortest path of the adjacent vertex is lesser than a total of a new path, don’t update the new path but update the shortest path of the adjacent vertex. Here, there are two adjacent vertices of vertex 40 and those weights are 5 and 7, but the new path is 1 + 5 =6 greater than the shortest path of adjacent vertex of the starting vertex so ignore it. Then add the shortest path of adjacent vertex of the starting vertex in the shortest path.
Step 3: Repeat until all the vertices have been visited. Then we got the shortest path
Implement Dijkstra’s Shortest Path Algorithm in Java
Here, we reuse the source code from the preview post Prim’s algorithm for minimum spanning tree. Then we just add two methods to demo Dijkstra’s algorithm. Let see the program below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
// Simple program implements a Graph in adjacency matrix import java.util.*; class Graph { private int size; private int adjMatrix[][]; Graph(int s){ this.size = s; adjMatrix = new int[size][size]; } public int[][] getAdjMatrix(){ return adjMatrix; } // adds a new edge to the graph public void addEdge(int i, int j, int weighted) { adjMatrix[i][j] = weighted; adjMatrix[j][i] = weighted; } // remove a edge to the graph public void removeEdge(int i, int j) { adjMatrix[i][j] = -1; adjMatrix[j][i] = -1; } // get graph size public int size() { return this.size; } // Displays the adjancency matrix of graph. public String toString() { StringBuilder s = new StringBuilder(); for (int i = 0; i < size; i++) { s.append(i + ": "); for (int j : adjMatrix[i]) { s.append((j) + " "); } s.append("\n"); } return s.toString(); } //find the vertex with minimum weight which is not included in MST int getMinDist(Boolean [] spArray, int [] indexArray){ int minIndex = Integer.MAX_VALUE; int index = -1; for (int i = 0; i <size ; i++) { if(spArray[i]==false && minIndex>indexArray[i]){ minIndex = indexArray[i]; index = i; } } return index; } // Method implements Dijkstra algorithm with single shortest path int[] dijkstra(int matrix[][], int start) { // array stores a shortest path of graph from vertex start int shortestPath[] = new int[size]; // array keeps track which vertex is put in shortest path Boolean spArray[] = new Boolean[size]; // Initialize all distances as INFINITE for shortestPath // and spArray[] as false since no one is put yet for (int i = 0; i < size; i++) { shortestPath[i] = Integer.MAX_VALUE; spArray[i] = false; } // Set distance of start vertex from itself is always 0 shortestPath[start] = 0; // Certainly, shortestPath will include all vertices of graph in this case. // So we take a loop with graph size to find shortest path. for (int i = 0; i < size - 1; i++) { // Find the minimum distance vertex in shortest path // Apparently, start vertex is chosen firstly int u = getMinDist(spArray, shortestPath); // Then mark the start vertex as processed spArray[u] = true; // Update shortestPath value of the adjacent vertices of the // picked vertex. // Keep finding the minimum distance vertex from the adjacent vertices for (int v = 0; v < size; v++) { // Just update shortestPath[v] in case: if (!spArray[v] && matrix[u][v] != 0 //it is not in spArray, u and v are adjacent && shortestPath[u] != Integer.MAX_VALUE// a distance is not infinite //total weight of path from start vertex to v through u is smaller than current value of shortestPath[v] && shortestPath[u] + matrix[u][v] < shortestPath[v] ) { shortestPath[v] = shortestPath[u] + matrix[u][v]; } } } return shortestPath; } } // Main class public class Main { public static void main(String args[]) { // create new graph instance Graph g = new Graph(4); // the create an array of vertices int[] vertices = new int[g.size()]; vertices[0] = 20; vertices[1] = 30; vertices[2] = 10; vertices[3] = 40; // sort vertices array // then use binary search algorthim to get the index of vertices Arrays.sort(vertices); System.out.println("Sorted vertices array: " +Arrays.toString(vertices)); int index20 = Arrays.binarySearch(vertices,20); int index10 = Arrays.binarySearch(vertices,10); int index30 = Arrays.binarySearch(vertices,30); int index40 = Arrays.binarySearch(vertices,40); //Now we create a graph from the corresponding indexes of vertices, // edges are added. g.addEdge(index10, index20,3); g.addEdge(index10, index40,1); g.addEdge(index20, index30,4); g.addEdge(index20, index40,5); g.addEdge(index30, index40,7); // print the graph. System.out.println("Here is the graph:\n" + g.toString()); int[][] graph = g.getAdjMatrix(); int[] dist = g.dijkstra(g.getAdjMatrix(),index10); System.out.println("Vertex \t\t Distance from Start Vertex"); for (int i = 0; i < dist.length; i++) System.out.println(vertices[i] + " \t\t " + dist[i]); } } |
Here is output of the above program:
Time Complexity
In this tutorial Dijkstra’s Shortest Path Algorithm in Java, we use a graph in adjacent matrix so time complexity of the above implementation is O(V2)
That’s all about Dijkstra’s Shortest Path Algorithm in Java.
References
Graph Data Structure in Java
