Even though Dr. Edsger W. Dijkstra invented the Dijkstra Algorithm in 20 minutes without pencil and paper, Dijkstra’s algorithm is the most popular shortest-path-finding algorithm in computer science.
This algorithm is used to find the shortest path between two nodes in a weighted graph. A real-life use case for such an algorithm would be a navigation app like Google Maps.
In this guide, you will learn how Dijkstra’s Algorithm works and how it is implemented in Java. Keep reading!
Dijkstra's Algorithm Explained
The Different Types of Graphs
Have a look at the following two graphs:
Notice that one of the graphs has directed connections between the nodes (weights), whereas the other has undirected connections (weights).
In directed graphs, be careful to only choose ways between nodes that are in the right direction.
For example, in the second graph, you cannot directly get from node B to node D.
How Dijkstra's Algorithm Finds the Shortest Path
Let’s take the undirected graph from above as an example.
The first step is to create a table with as many rows as we’ve got nodes and 2 columns. The first column represents the shortest known weight to get to a node. The second column holds the node where we come from (the previous node).
Here’s an example of how the table should look like:
Next, we are going to assign every node in the table a weight of infinity, except for the starting node. The starting node is assigned a weight of zero and itself as the previous node.
Let’s say node A is our starting node in this example.
In addition to this table, we also need a list to keep track of the nodes we have already visited.
Now we can get started with finding the shortest path.
Dijkstra’s algorithm terminates if all nodes have been visited.
We begin by looking at the starting node, node A.
In our table we check whether the weight for getting to a node can be reduced.
As all weights, except node A, are set to infinity, we update all of them.
Now, the previous node is set to A and A has been visited.
The next node we visit is the one that has the lowest weight in our table and hasn’t been visited yet. In this case, that’s node E.
Let’s check again whether any weights can be updated.
We can get from E to B with a weight of 1. However, we need to add the weight to get to E as well.
Hence, our new weight for getting to B over E is 3.
Don’t forget to update the visited nodes list!
The shortest weights are now B and C. Because the weights are the same, simply choose one of them.
The only weight we can update is D.
Because B has a weight of 3 and B to D has a weight of 2, the combined weight is now 5 and the previous node of D is B.
When visiting node C, no weight is updated. So we simply add C to our visited nodes list and go on.
Again, node D doesn’t reveal any lower weights. Add D to the visited nodes list.
As all nodes have been visited, the algorithm terminates and our table of shortest paths is complete.
If you now want to know the shortest way to get from A to D, look at node D in the table. The total weight of getting from A to D is 5. To get there, we track back the previous nodes.
D -> B -> E -> A
When reversing this list, we get our shortest path from A to D.
A -> E -> B -> D
Dijkstra's Algorithm in Java
Now that we know how the algorithm works, we can get to implementing Dijkstra’s Algorithm in Java.
Recommended: How to Install the Java JDK on Windows & Linux
How Graphs are Implemented in Code
You might wonder how to convert a visual graph with connected nodes and weights into Java code.
This can be done relatively easily using an adjacency matrix.
The adjacency matrix is a square matrix, which represents all the nodes and all the connections between those nodes.
Here’s how it works:
Notice that the weights in the matrix are mirrored on the diagonal from the top left to the top right. That’s because the graph is undirected and connections always work in both ways.
If the graph was directed instead, it would look like this:
However let’s work with our undirected graph in this guide.
Implemented in Java code, our adjacency matrix would look like this:
int[][] adjacencyMatrix = {
{ 0, 5, 3, 0, 2 },
{ 5, 0, 0, 2, 1 },
{ 3, 0, 0, 6, 0 },
{ 0, 2, 6, 0, 0 },
{ 2, 1, 0, 0, 0 }
};
Initializing the Table
In order to run Dijkstra’s Algorithm in Java, we need the table with all the shortest paths and the previous nodes.
However, instead of assigning the weights a value of infinity, we assign them a value of -1. Also, the previous nodes are assigned -1.
Of course, the starting node is assigned a weight of 0 and itself as a previous node.
int[][] table = new int[adjacencyMatrix.length][2];
// initialize table
for (int i = 0; i < table.length; i++) { // loop through all nodes
if (i == startNode) { // treat the start node differently
table[i][0] = 0;
table[i][1] = start;
}
else {
table[i][0] = -1;
table[i][1] = -1;
}
}
Visiting all Nodes
To visit all nodes, we define an integer variable that holds the node we are currently visiting. Also, we need an ArrayList that keeps track of all the nodes that have been visited already.
In a while-loop that finishes when the length of the visited nodes list is equal to the length of the adjacency matrix, we check all weights of a node and whether they can update the table.
Last but not least, we select the next node with the shortest weight that hasn’t been visited yet.
ArrayList<Integer> visited = new ArrayList<>();
int node = startNode;
while (visited.size() != adjacencyMatrix.length) { // terminate if all nodes have been visited
// visit node
for (int i = 0; i < adjacencyMatrix[0].length; i++) { // loop through all weights of a node
int weight = adjacencyMatrix[node][i];
if (weight != 0) {
weight += table[node][0]; // calculate the final weight
if ((weight < table[i][0] || table[i][0] == -1) && !visited.contains(i)) { // if the calculated weight is shorter and the node hasn't been visited
table[i][0] = weight;
table[i][1] = node;
}
}
}
visited.add(node);
// visit next node with the shortest path
int min = 5000;
for (int y = 0; y < table.length; y++) {
if (table[y][0] != -1 && table[y][0] != 0) {
if (table[y][0] < min && !visited.contains(y)) {
min = table[y][0];
node = y;
}
}
}
}
Complete Java Code
When running the code, use numbers instead of characters for your nodes. For example, node A is number 0, node B is number 1, and so on.
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
int[][] adjacencyMatrix = {
{ 0, 5, 3, 0, 2 },
{ 5, 0, 0, 2, 1 },
{ 3, 0, 0, 6, 0 },
{ 0, 2, 6, 0, 0 },
{ 2, 1, 0, 0, 0 }
};
dijkstra(adjacencyMatrix, 0, 3);
}
public static int[][] dijkstra(int[][] adjacencyMatrix, int start, int destination) {
int[][] table = new int[adjacencyMatrix.length][2];
ArrayList<Integer> visited = new ArrayList<>();
int node = start;
// initialize table
for (int i = 0; i < table.length; i++) {
if (i == start) {
table[i][0] = 0;
table[i][1] = start;
}
else {
table[i][0] = -1;
table[i][1] = -1;
}
}
while (visited.size() != adjacencyMatrix.length) {
// visit node
for (int i = 0; i < adjacencyMatrix[0].length; i++) {
int weight = adjacencyMatrix[node][i];
if (weight != 0) {
weight += table[node][0];
if ((weight < table[i][0] || table[i][0] == -1) && !visited.contains(i)) {
table[i][0] = weight;
table[i][1] = node;
}
}
}
visited.add(node);
// visit next node with the shortest path
int min = 5000;
for (int y = 0; y < table.length; y++) {
if (table[y][0] != -1 && table[y][0] != 0) {
if (table[y][0] < min && !visited.contains(y)) {
min = table[y][0];
node = y;
}
}
}
}
// print shortest route
printShortestPath(table, start, destination);
System.out.println(" -> " + destination);
return table;
}
public static void printShortestPath(int[][] table, int start, int destination) {
if (table[destination][1] != start) {
printShortestPath(table, start, table[destination][1]);
}
System.out.print((table[destination][1] != start ? " -> " : "") + table[destination][1]);
}
}
After running this code you should have the same output as in the explanation of the algorithm.
0 -> 4 -> 1 -> 3
A -> E -> B -> D
And that’s how Dijkstra’s Algorithm is implemented in Java!
It wasn’t even that difficult, right?
Thanks for reading and happy coding!