Calculate shortest paths in Java by implementing Dijkstra’s Algorithm

Conceived by Edsger W. Dijsktra in 1956 and published three years later, Dijkstra’s algorithm is a one of the most known algorithms for finding the shortest paths between nodes in a graph. This algorithm is applied in a lot of domains. For example, once you have represented road networks in a graph, it becomes easy to calculate shortest paths inside this graph by applying Dijkstra’s algorithm.

In Pseudocode, Dijkstra’s algorithm can be translated like that :

Image for post
Image for post

In this tutorial, you’re going to learn how to implement Disjkstra’s Algorithm in Java. In a first time, we need to create objects to represent a graph before to apply Dijkstra’s Algorithm.

1. Represent Edges

In a graph, Edges are used to link two Nodes. So, an Edge is linked to two nodes and have a length that is an integer here. It’s useful to represent a distance for example in road networks.

2. Represent Nodes

Now, it’s time to represent Nodes. A Node must have a list of Edge that are linked to it. Besides, it must have a field to define if the Node has been visited or no. It will be useful when we will apply Dijkstra’s Algorithm to calculate shortest paths in the graph. Last, we need to define a distanceFromSource field that will represent the result for that Node of the algorithm.

3. Represent a Graph

Now that we have Edges and Nodes, we can represent a Graph that must contain Edges and Nodes. In the constructor, we take an array of Edges and we build the Graph by creating corresponding Nodes. The Dijkstra’s Algorithm is implemented in the calculateShortestDistances() method. It’s really the application of the Pseudocode algorithm displayed previously. Our Graph class is like that :

In the printResult() method, we have just to iterate on the Nodes’ array and display the distanceFromSource property value.

4. Assemble the puzzle in a Main class

Now, it’s time to test our implementation of the Dijkstra’s Algorithm. So, we consider the following graph :

Image for post
Image for post

We define that graph in our Main class and then we have just to call the calculateShortestDistances() method. Last, we need to print the result of the algorithm.

Result is detailed in the following figure.

Image for post
Image for post

Like you can see, our implementation works well !

5. Bonus

As a Bonus, you can enjoy the following tutorial in video :

Written by

Entrepreneur / Developer / Blogger / Author. In Bitcoin We Trust:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store