 # 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 : 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.

package com.ssaurel.dijsktra;public class Edge { private int fromNodeIndex; private int toNodeIndex; private int length; public Edge(int fromNodeIndex, int toNodeIndex, int length) { this.fromNodeIndex = fromNodeIndex; this.toNodeIndex = toNodeIndex; this.length = length; } public int getFromNodeIndex() { return fromNodeIndex; } public int getToNodeIndex() { return toNodeIndex; } public int getLength() { return length; } // determines the neighbouring node of a supplied node, based on the two nodes connected by this edge public int getNeighbourIndex(int nodeIndex) { if (this.fromNodeIndex == nodeIndex) { return this.toNodeIndex; } else { return this.fromNodeIndex; } }}

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.

package com.ssaurel.dijsktra;import java.util.ArrayList;public class Node { private int distanceFromSource = Integer.MAX_VALUE; private boolean visited; private ArrayList<Edge> edges = new ArrayList<Edge>(); // now we must create edges public int getDistanceFromSource() { return distanceFromSource; } public void setDistanceFromSource(int distanceFromSource) { this.distanceFromSource = distanceFromSource; } public boolean isVisited() { return visited; } public void setVisited(boolean visited) { this.visited = visited; } public ArrayList<Edge> getEdges() { return edges; } public void setEdges(ArrayList<Edge> edges) { this.edges = edges; }}

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 : 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.

package com.ssaurel.dijsktra;public class Main { public static void main(String args) { Edge edges = { new Edge(0, 2, 1), new Edge(0, 3, 4), new Edge(0, 4, 2), new Edge(0, 1, 3), new Edge(1, 3, 2), new Edge(1, 4, 3), new Edge(1, 5, 1), new Edge(2, 4, 1), new Edge(3, 5, 4), new Edge(4, 5, 2), new Edge(4, 6, 7), new Edge(4, 7, 2), new Edge(5, 6, 4), new Edge(6, 7, 5) }; Graph g = new Graph(edges); g.calculateShortestDistances(); g.printResult(); // let’s try it ! }}

Result is detailed in the following figure. Like you can see, our implementation works well !

5. Bonus

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