Dijkstra’s Algorithm is a powerful algorithm used in graph theory to find the shortest path between two vertices. It was developed by Edsger Dijkstra, a Dutch computer scientist, in 1956 and is now one of the most widely used algorithms in computer science. It is used in many applications and is often used to find the shortest path between two locations on a map. Dijkstra’s Algorithm is highly efficient and has a time complexity of O(V^2 + E), where V is the number of vertices and E is the number of edges in the graph. In this article, we will discuss how Dijkstra’s Algorithm works, its time and space complexity, and how to implement it in Java.
How Dijkstra’s Algorithm Works
Dijkstra’s Algorithm is a greedy algorithm that works by starting at one vertex and exploring all possible paths from it to other vertices. As it explores each path, it keeps track of the cost of each path and the total cost of the path so far. Once all the paths have been explored, it will have found the shortest path from the starting vertex to every other vertex.
The algorithm works by using a priority queue. This queue is used to store all the paths that have been explored and the total cost of each path. The priority queue is sorted based on the cost of each path, so the path with the lowest cost is always at the top of the queue. Then, the algorithm takes the path at the top of the queue and explores all possible paths from that vertex. After exploring all the paths, the algorithm updates the total cost of each path and puts them back in the priority queue. This process is repeated until the queue is empty.
Time Complexity
The time complexity of Dijkstra’s Algorithm is O(V^2 + E), where V is the number of vertices in the graph and E is the number of edges. This means that the algorithm can be used to solve large graphs in a reasonable amount of time.
Space Complexity
The space complexity of Dijkstra’s Algorithm is O(V), where V is the number of vertices in the graph. This means that the algorithm requires a relatively small amount of memory to run.
Implementing Dijkstra’s Algorithm in Java
Now that we have discussed how Dijkstra’s Algorithm works and its time and space complexity, let’s look at how to implement it in Java. First, we need to define a few classes and methods.
We can start by defining a Node class which will represent each vertex in the graph. The Node class should contain two fields: an integer ID and a HashMap which will store the edges of the graph.
public class Node {
int id;
HashMap<Node, Integer> edges;
//constructor and other methods
}
Next, we need to define a Graph class which will store the nodes of the graph. The Graph class should contain a HashMap which maps node IDs to Node objects.
public class Graph {
HashMap<Integer, Node> nodes;
//constructor and other methods
}
We also need to define a PriorityQueue class which will store the paths explored by the algorithm and the total cost of each path. The PriorityQueue class should contain a Comparator which will compare the cost of two paths.
public class PriorityQueue {
Comparator<Path> comparator;
//constructor and other methods
}
Finally, we need to define a Path class which will represent a path from one vertex to another. The Path class should contain two fields: a List of Nodes which will store the nodes in the path and an integer which will store the total cost of the path.
public class Path {
List<Node> nodes;
int cost;
//constructor and other methods
}
Now that we have defined the necessary classes, we can start implementing the algorithm. We can start by initializing the graph with the nodes and edges.
Graph graph = new Graph();
//Add nodes to graph
//Add edges to graph
Next, we need to initialize the priority queue with the starting path. The starting path should contain only the starting node and have a cost of 0.
PriorityQueue queue = new PriorityQueue();
Path startPath = new Path();
startPath.nodes.add(graph.nodes.get(start));
startPath.cost = 0;
queue.add(startPath);
We can then start looping through the queue until it is empty. In each loop, we need to take the path with the lowest cost from the queue, explore all the edges from the last node in the path, and add the paths to the queue.
while(!queue.isEmpty()) {
Path currPath = queue.poll();
//Explore all edges from the last node in the path
Node lastNode = currPath.nodes.get(currPath.nodes.size() - 1);
for(Node neighbor : lastNode.edges.keySet()) {
//Calculate cost of the path
int cost = currPath.cost + lastNode.edges.get(neighbor);
//Create a new path
Path newPath = new Path();
newPath.nodes.addAll(currPath.nodes);
newPath.nodes.add(neighbor);
newPath.cost = cost;
//Add the new path to the queue
queue.add(newPath);
}
}
Once the priority queue is empty, the algorithm is complete and we will have found the shortest path from the starting vertex to every other vertex.
Here is another implementation of Dijkstra’s Algorithm in Java using an adjacency matrix. The following code example shows how to create an adjacency matrix and use it to find the shortest path between two nodes in a graph.
import java.util.ArrayList;
import java.util.List;
public class DijkstraAlgorithm {
// Create an adjacency matrix
int[][] adjMatrix;
// Create a list of visited nodes
List<Integer> visited = new ArrayList<>();
// Create a list of unvisited nodes
List<Integer> unvisited = new ArrayList<>();
// Create an array to store distances
int[] distances;
// Create a variable to store the starting node
int startNode;
// Create a variable to store the destination node
int destNode;
public DijkstraAlgorithm(int[][] adjMatrix, int startNode, int destNode) {
this.adjMatrix = adjMatrix;
this.startNode = startNode;
this.destNode = destNode;
this.distances = new int[adjMatrix.length];
// Set all distances to infinity
for (int i = 0; i < distances.length; i++) {
distances[i] = Integer.MAX_VALUE;
}
// Set the distance of the start node to 0
distances[startNode] = 0;
// Add all nodes to the unvisited list
for (int i = 0; i < adjMatrix.length; i++) {
unvisited.add(i);
}
}
public void findShortestPath() {
// Get the node with the smallest distance
int minNode = getMinNode();
// If the minNode is the destination node, we have found the shortest path
if (minNode == destNode) {
return;
}
// Move the minNode from the unvisited list to the visited list
visited.add(minNode);
unvisited.remove(minNode);
// Check all adjacent nodes of the minNode
for (int i = 0; i < adjMatrix.length; i++) {
// If the adjacent node is not visited and the edge weight is not 0
if (!visited.contains(i) && adjMatrix[minNode][i] != 0) {
// Calculate the distance of the adjacent node
int newDistance = distances[minNode] + adjMatrix[minNode][i];
// If the new distance is less than the current distance, update it
if (newDistance < distances[i]) {
distances[i] = newDistance;
}
}
}
// Repeat the process until the destination node is reached
findShortestPath();
}
// Find the node with the smallest distance
private int getMinNode() {
int minNode = 0;
int minDistance = Integer.MAX_VALUE;
for (int i = 0; i < distances.length; i++) {
if (unvisited.contains(i) && distances[i] < minDistance) {
minNode = i;
minDistance = distances[i];
}
}
return minNode;
}
// Print the distance of each node
public void printDistances() {
for (int i = 0; i < distances.length; i++) {
System.out.println("Distance of node " + i + ": " + distances[i]);
}
}
public static void main(String[] args) {
int[][] adjMatrix = {
{0, 8, 0, 3},
{0, 0, 2, 5},
{0, 0, 0, 4},
{0, 0, 0, 0}
};
DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(adjMatrix, 0, 3);
dijkstra.findShortestPath();
dijkstra.printDistances();
}
}
Conclusion
In this article, we discussed Dijkstra’s Algorithm and how to implement it in Java. Dijkstra’s Algorithm is a powerful algorithm used in graph theory to find the shortest path between two vertices. It has a time complexity of O(V^2 + E) and a space complexity of O(V), where V is the number of vertices and E is the number of edges in the graph. We discussed how the algorithm works and then looked at how to implement it in Java.
Exercises
Write a Java program to implement Dijkstra’s Algorithm using an adjacency list.
import java.util.ArrayList;
import java.util.List;
public class DijkstraAlgorithm {
// Create an adjacency list
List<List<int[]>> adjList;
// Create a list of visited nodes
List<Integer> visited = new ArrayList<>();
// Create a list of unvisited nodes
List<Integer> unvisited = new ArrayList<>();
// Create an array to store distances
int[] distances;
// Create a variable to store the starting node
int startNode;
// Create a variable to store the destination node
int destNode;
public DijkstraAlgorithm(List<List<int[]>> adjList, int startNode, int destNode) {
this.adjList = adjList;
this.startNode = startNode;
this.destNode = destNode;
this.distances = new int[adjList.size()];
// Set all distances to infinity
for (int i = 0; i < distances.length; i++) {
distances[i] = Integer.MAX_VALUE;
}
// Set the distance of the start node to 0
distances[startNode] = 0;
// Add all nodes to the unvisited list
for (int i = 0; i < adjList.size(); i++) {
unvisited.add(i);
}
}
public void findShortestPath() {
// Get the node with the smallest distance
int minNode = getMinNode();
// If the minNode is the destination node, we have found the shortest path
if (minNode == destNode) {
return;
}
// Move the minNode from the unvisited list to the visited list
visited.add(minNode);
unvisited.remove(minNode);
// Check all adjacent nodes of the minNode
for (int[] pair : adjList.get(minNode)) {
// If the adjacent node is not visited
if (!visited.contains(pair[0])) {
// Calculate the distance of the adjacent node
int newDistance = distances[minNode] + pair[1];
// If the new distance is less than the current distance, update it
if (newDistance < distances[pair[0]]) {
distances[pair[0]] = newDistance;
}
}
}
// Repeat the process until the destination node is reached
findShortestPath();
}
// Find the node with the smallest distance
private int getMinNode() {
int minNode = 0;
int minDistance = Integer.MAX_VALUE;
for (int i = 0; i < distances.length; i++) {
if (unvisited.contains(i) && distances[i] < minDistance) {
minNode = i;
minDistance = distances[i];
}
}
return minNode;
}
// Print the distance of each node
public void printDistances() {
for (int i = 0; i < distances.length; i++) {
System.out.println("Distance of node " + i + ": " + distances[i]);
}
}
public static void main(String[] args) {
List<List<int[]>> adjList = new ArrayList<>();
// Add edges to the adjacency list
adjList.add(List.of(new int[] {1, 8}, new int[] {3, 3}));
adjList.add(List.of(new int[] {2, 2}, new int[] {3, 5}));
adjList.add(List.of(new int[] {3, 4}));
DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(adjList, 0, 3);
dijkstra.findShortestPath();
dijkstra.printDistances();
}
}
Write a Java program to implement Dijkstra’s Algorithm using a priority queue.
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class DijkstraAlgorithm {
// Create an adjacency matrix
int[][] adjMatrix;
// Create a list of visited nodes
List<Integer> visited = new ArrayList<>();
// Create a priority queue to store unvisited nodes
Queue<int[]> unvisited = new PriorityQueue<>((a, b) -> a[1] - b[1]);
// Create an array to store distances
int[] distances;
// Create a variable to store the starting node
int startNode;
// Create a variable to store the destination node
int destNode;
public DijkstraAlgorithm(int[][] adjMatrix, int startNode, int destNode) {
this.adjMatrix = adjMatrix;
this.startNode = startNode;
this.destNode = destNode;
this.distances = new int[adjMatrix.length];
// Set all distances to infinity
for (int i = 0; i < distances.length; i++) {
distances[i] = Integer.MAX_VALUE;
}
// Set the distance of the start node to 0
distances[startNode] = 0;
// Add all nodes to the unvisited priority queue
for (int i = 0; i < adjMatrix.length; i++) {
unvisited.add(new int[] {i, distances[i]});
}
}
public void findShortestPath() {
// Get the node with the smallest distance
int minNode = getMinNode();
// If the minNode is the destination node, we have found the shortest path
if (minNode == destNode) {
return;
}
// Move the minNode from the unvisited list to the visited list
visited.add(minNode);
// Check all adjacent nodes of the minNode
for (int i = 0; i < adjMatrix.length; i++) {
// If the adjacent node is not visited and the edge weight is not 0
if (!visited.contains(i) && adjMatrix[minNode][i] != 0) {
// Calculate the distance of the adjacent node
int newDistance = distances[minNode] + adjMatrix[minNode][i];
// If the new distance is less than the current distance, update it
if (newDistance < distances[i]) {
distances[i] = newDistance;
unvisited.add(new int[] {i, distances[i]});
}
}
}
// Repeat the process until the destination node is reached
findShortestPath();
}
// Find the node with the smallest distance
private int getMinNode() {
int minNode = unvisited.peek()[0];
unvisited.poll();
return minNode;
}
// Print the distance of each node
public void printDistances() {
for (int i = 0; i < distances.length; i++) {
System.out.println("Distance of node " + i + ": " + distances[i]);
}
}
public static void main(String[] args) {
int[][] adjMatrix = {
{0, 8, 0, 3},
{0, 0, 2, 5},
{0, 0, 0, 4},
{0, 0, 0, 0}
};
DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(adjMatrix, 0, 3);
dijkstra.findShortestPath();
dijkstra.printDistances();
}
}
What is the time complexity of Dijkstra’s Algorithm?
The time complexity of Dijkstra’s Algorithm is O(V^2 + E), where V is the number of vertices in the graph and E is the number of edges. This means that the algorithm can be used to solve large graphs in a reasonable amount of time.
Create a graph with 5 vertices and 7 edges and implement Dijkstra’s Algorithm to find the shortest path between two nodes.
class Graph {
// A List of Lists to represent an adjacency list
List<List<Node>> adjList = null;
// Constructor
Graph(List<Edge> edges, int N)
{
adjList = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
adjList.add(i, new ArrayList<>());
}
// add edges to the undirected graph
for (Edge edge : edges) {
adjList.get(edge.src).add(edge.dest);
adjList.get(edge.dest).add(edge.src);
}
}
// Dijkstra's Algorithm
public void dijkstra(int src, int N)
{
// create a priority queue to store nodes and their
// distance from the source node
PriorityQueue<Node> pq = new PriorityQueue<>(N,
(a, b) -> Integer.compare(a.cost, b.cost));
// create an array to store the shortest distance
// from the source node to each node
int[] dist = new int[N];
// initialize the distance array
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// add the source node to the priority queue
pq.add(new Node(src, 0));
// loop until the priority queue is empty
while (!pq.isEmpty()) {
// get the node with the smallest distance
Node node = pq.poll();
// explore the adjacent nodes of the current node
List<Node> adjNodes = adjList.get(node.vertex);
for (Node adjNode : adjNodes) {
// calculate the distance of the adjacent node
int newDist = dist[node.vertex] + adjNode.cost;
// if the new distance is smaller than the current distance
// update the distance and add the adjacent node to the priority queue
if (dist[adjNode.vertex] > newDist) {
dist[adjNode.vertex] = newDist;
pq.add(new Node(adjNode.vertex, newDist));
}
}
}
// print the shortest distances stored in dist[]
printSolution(dist, N);
}
// Helper function to print the solution
public void printSolution(int[] dist, int N)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < N; ++i)
System.out.println(i + "\t\t" + dist[i]);
}
// Driver Code
public static void main(String[] args)
{
// input: 5 vertices and 7 edges
int N = 5;
List<Edge> edges = Arrays.asList(
new Edge(0, 1, 9), new Edge(1, 2, 10),
new Edge(0, 4, 15), new Edge(2, 4, 11),
new Edge(3, 2, 6), new Edge(1, 3, 7),
new Edge(3, 4, 9));
// construct graph
Graph graph = new Graph(edges, N);
// Run Dijkstra's Algorithm from vertex 0
graph.dijkstra(0, N);
}
}
class Edge {
int src, dest, cost;
public Edge(int src, int dest, int cost)
{
this.src = src;
this.dest = dest;
this.cost = cost;
}
}
class Node {
int vertex, cost;
public Node(int vertex, int cost)
{
this.vertex = vertex;
this.cost = cost;
}
}
Create a graph with 8 vertices and 12 edges and implement Dijkstra’s Algorithm to find the shortest path between two nodes.
class Graph {
// A List of Lists to represent an adjacency list
List<List<Node>> adjList = null;
// Constructor
Graph(List<Edge> edges, int N)
{
adjList = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
adjList.add(i, new ArrayList<>());
}
// add edges to the undirected graph
for (Edge edge : edges) {
adjList.get(edge.src).add(edge.dest);
adjList.get(edge.dest).add(edge.src);
}
}
// Dijkstra's Algorithm
public void dijkstra(int src, int N)
{
// create a priority queue to store nodes and their
// distance from the source node
PriorityQueue<Node> pq = new PriorityQueue<>(N,
(a, b) -> Integer.compare(a.cost, b.cost));
// create an array to store the shortest distance
// from the source node to each node
int[] dist = new int[N];
// initialize the distance array
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// add the source node to the priority queue
pq.add(new Node(src, 0));
// loop until the priority queue is empty
while (!pq.isEmpty()) {
// get the node with the smallest distance
Node node = pq.poll();
// explore the adjacent nodes of the current node
List<Node> adjNodes = adjList.get(node.vertex);
for (Node adjNode : adjNodes) {
// calculate the distance of the adjacent node
int newDist = dist[node.vertex] + adjNode.cost;
// if the new distance is smaller than the current distance
// update the distance and add the adjacent node to the priority queue
if (dist[adjNode.vertex] > newDist) {
dist[adjNode.vertex] = newDist;
pq.add(new Node(adjNode.vertex, newDist));
}
}
}
// print the shortest distances stored in dist[]
printSolution(dist, N);
}
// Helper function to print the solution
public void printSolution(int[] dist, int N)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < N; ++i)
System.out.println(i + "\t\t" + dist[i]);
}
// Driver Code
public static void main(String[] args)
{
// input: 8 vertices and 12 edges
int N = 8;
List<Edge> edges = Arrays.asList(
new Edge(0, 1, 8), new Edge(1, 2, 10),
new Edge(2, 3, 3), new Edge(3, 4, 6),
new Edge(4, 5, 7), new Edge(5, 6, 9),
new Edge(6, 7, 5), new Edge(7, 0, 4),
new Edge(1, 4, 15), new Edge(2, 5, 11),
new Edge(3, 6, 6), new Edge(4, 7, 9));
// construct graph
Graph graph = new Graph(edges, N);
// Run Dijkstra's Algorithm from vertex 0
graph.dijkstra(0, N);
}
}
class Edge {
int src, dest, cost;
public Edge(int src, int dest, int cost)
{
this.src = src;
this.dest = dest;
this.cost = cost;
}
}
class Node {
int vertex, cost;
public Node(int vertex, int cost)
{
this.vertex = vertex;
this.cost = cost;
}
}