Dijkstra’s algorithm is a popular technique used to find the shortest path between nodes in a graph. In this blog, we’ll explore how to implement Dijkstra’s algorithm in Java. Even if you’re new to Java or programming in general, this guide will walk you through the code step by step.
What You Need to Know
Before diving into the code, you should have a basic understanding of:
- Java Basics: How to write and run simple Java programs.
- Graphs: A graph consists of vertices (or nodes) connected by edges. An edge has a weight, representing the cost of traveling between two nodes.
- Priority Queues: A data structure that allows efficient retrieval of the smallest element.
If you’re unfamiliar with these concepts, don’t worry—I’ll explain everything you need to know as we go along.
Dijkstra’s Algorithm: Concept
- Initialization: Start at the source node and set the initial distances to all other nodes as infinity, except the source node itself, which has a distance of 0.
- Visiting Nodes: Visit the node with the smallest known distance. Update the distances to its neighboring nodes if a shorter path is found.
- Repeat: Continue this process until all nodes have been visited.
Let’s Get Coding!
Here’s the complete Java code for Dijkstra’s algorithm. We’ll break it down step by step afterward.
import java.util.*;
class Graph {
private final int vertices; // Number of vertices in the graph
private final List<List<Node>> adjacencyList; // Adjacency list to represent the graph
// Node class to represent a graph node
static class Node implements Comparable<Node> {
int vertex; // The node's identifier
int weight; // The weight of the edge to this node
// Constructor
Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
// Compare nodes by weight for the priority queue
@Override
public int compareTo(Node other) {
return Integer.compare(this.weight, other.weight);
}
}
// Graph constructor
public Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new LinkedList<>());
}
}
// Method to add an edge to the graph
public void addEdge(int source, int destination, int weight) {
adjacencyList.get(source).add(new Node(destination, weight));
adjacencyList.get(destination).add(new Node(source, weight)); // For undirected graph
}
// Dijkstra's algorithm
public void dijkstra(int startVertex) {
PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
int[] distances = new int[vertices];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[startVertex] = 0;
priorityQueue.add(new Node(startVertex, 0));
while (!priorityQueue.isEmpty()) {
Node currentNode = priorityQueue.poll();
int currentVertex = currentNode.vertex;
// Traverse through all adjacent nodes
for (Node neighbor : adjacencyList.get(currentVertex)) {
int newDist = distances[currentVertex] + neighbor.weight;
// If new distance is shorter
if (newDist < distances[neighbor.vertex]) {
distances[neighbor.vertex] = newDist;
priorityQueue.add(new Node(neighbor.vertex, newDist));
}
}
}
// Print shortest distances
System.out.println("Shortest distances from vertex " + startVertex);
for (int i = 0; i < vertices; i++) {
System.out.println("To vertex " + i + " - " + distances[i]);
}
}
public static void main(String[] args) {
int vertices = 5; // Total number of vertices in the graph
Graph graph = new Graph(vertices);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 5);
graph.addEdge(1, 2, 1);
graph.addEdge(4, 1, 3);
graph.addEdge(4, 2, 9);
graph.addEdge(4, 3, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 2, 6);
graph.dijkstra(0);
}
}Breaking Down the Code
1. Graph Class: Setting Up the Graph
class Graph {
private final int vertices; // Number of vertices in the graph
private final List<List<Node>> adjacencyList; // Adjacency list to represent the graphvertices: This variable holds the number of vertices (nodes) in the graph.adjacencyList: This list holds the edges of each vertex. Each vertex has a list of neighboring nodes.
public Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new LinkedList<>());
}
}Graph(int vertices): This constructor initializes the graph with a given number of vertices and creates an empty adjacency list for each vertex.
2. Node Class: Representing Graph Nodes
static class Node implements Comparable<Node> {
int vertex; // The node's identifier
int weight; // The weight of the edge to this node
Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.weight, other.weight);
}
}Node(int vertex, int weight): This constructor sets the vertex identifier and edge weight.compareTo(Node other): This method is used to compare nodes by their weights, which helps prioritize the nodes with the smallest weights in the priority queue.
3. addEdge Method: Adding Edges
public void addEdge(int source, int destination, int weight) {
adjacencyList.get(source).add(new Node(destination, weight));
adjacencyList.get(destination).add(new Node(source, weight)); // For undirected graph
}addEdge(int source, int destination, int weight): This method adds an edge from the source to the destination with the specified weight. Since our graph is undirected, it also adds the reverse edge.
4. dijkstra Method: Finding Shortest Paths
public void dijkstra(int startVertex) {
PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
int[] distances = new int[vertices];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[startVertex] = 0;
priorityQueue.add(new Node(startVertex, 0));PriorityQueue<Node> priorityQueue: This priority queue helps us always choose the node with the smallest known distance.int[] distances: This array holds the shortest known distances to each node from the start vertex. We initialize all distances to infinity (Integer.MAX_VALUE) except the start vertex, which is 0.
while (!priorityQueue.isEmpty()) {
Node currentNode = priorityQueue.poll();
int currentVertex = currentNode.vertex;
for (Node neighbor : adjacencyList.get(currentVertex)) {
int newDist = distances[currentVertex] + neighbor.weight;
if (newDist < distances[neighbor.vertex]) {
distances[neighbor.vertex] = newDist;
priorityQueue.add(new Node(neighbor.vertex, newDist));
}
}
}
}while (!priorityQueue.isEmpty()): This loop continues until we’ve visited all reachable nodes.Node currentNode = priorityQueue.poll(): We get the node with the smallest known distance.for (Node neighbor : adjacencyList.get(currentVertex)): We iterate through all the neighbors of the current node.int newDist = distances[currentVertex] + neighbor.weight: We calculate the distance to the neighbor through the current node.if (newDist < distances[neighbor.vertex]): If this new distance is shorter, we update the shortest known distance and add the neighbor to the priority queue with the new distance.
5. Main Method: Putting It All Together
public static void main(String[] args) {
int vertices = 5; // Total number of vertices in the graph
Graph graph = new Graph(vertices);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 5);
graph.addEdge(1, 2, 1);
graph.addEdge(4, 1, 3);
graph.addEdge(4, 2, 9);
graph.addEdge(4, 3, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 2, 6);
graph.dijkstra(0);
}int vertices = 5: We define a graph with 5 vertices.graph.addEdge(...): We add edges between vertices with specified weights.graph.dijkstra(0): We call thedijkstramethod to find the shortest paths from vertex 0.
Conclusion
Congratulations! You now have a working implementation of Dijkstra’s algorithm in Java. This algorithm is fundamental for solving many shortest path problems in real-world applications, such as finding the