Dijkstra’s Shortest Path Algorithm in Java, easy in 5 minutes

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.

Dijkstra's Shortest Path Algorithm in Java

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.

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 documentation


Graph Data Structure in Java

Please share it if you found this useful
Hide Buttons