Dijkstra's algorithm is a process to find the shortest paths from a single source node to all other nodes in a weighted graph. In this post we'll see the Java implementation of the Dijkstra's algorithm.
Some points about Dijkstra's algorithm
- Dijkstra's algorithm requires that all edge weights should be non-negative.
- It can be used to find the shortest path for both directed or undirected graphs.
- A greedy algorithm is defined as an algorithm that makes the locally optimal choice at each stage. Dijkstra's algorithm is classified as a greedy algorithm because, at each step the algorithm makes the locally optimal choice by picking one of the unvisited nodes with the smallest distance from the source.
How does Dijkstra's algorithm work
To start with, you need a data structure to keep track of visited nodes. You can use a boolean array for that, marking index of the visited node as true. Another data structure is needed to store distance of each node from the source node, for that you can use an array of type int.
A min heap to store immediate neighbours of any node and corresponding weights. For that PriorityQueue can be used.
Initially, array which stores distances should assign 0 to the source node and infinity to all the other nodes. As a substitute of infinity you may use Integer.MAX_VALUE
int[] dist = new int[graph.vertices]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;
In PriorityQueue add the source node with distance as 0.
Let's take the following undirected graph as an example with source node as 0.
In each iteration (for which condition is that PriorityQueue is not empty)
- Get the root of the min heap. Which means the head of the priority queue. In the first iteration it'll be 0. Let's call it c.
- Find the immediate neighbours of source node and verify the following for each neighbour node. Let’s call each
neighbour node v-
If the path through c to v is less than the currently stored distance to v if (dist[c] + weight between c and v < dist[v]) then store this new shorter distance as dist[v] dist[v] = dist[c] + w;
- Also add these neighbour nodes with their calculated distance from source node in PriorityQueue.
pq.add(new Edge(v, dist[v]));
If we take our example graph then immediate neighbours of 0 are node 1 and 4. So these two will be added to the priority queue and their distance from the source node will be updated in dist array.
dist array at this point- [0, 10, 2147483647, 2147483647, 5]
pq at this point [(1,10), (4,5)]
In next iteration, node 4 will be extracted from the pq (Because that has shorter distance). Immediate neighbours of 4 are 0 and 3. Note that, 0 is selected as an immediate neighbour when graph is an undirected graph. Since 0 is already visited so calculation won't be done for it.
For node 3 distance is checked using the above mentioned logic- if (dist[c] + weight between c and v < dist[v])
dist[4] + 50 < dist[3] which translates to- 5+50 < 2147483647
So, now the dist array is- [0, 10, 2147483647, 55, 5]
pq at this point [(1,10), (3,50)]
In next iteration node 1 will be extracted from the pq with immediate neighbours as 0, 2 and 3.
For node 2 distance is calculated as dist[1] + 30 < 2147483647 which translates to- 10+30=40
And node 3 distance is calculated as dist[1] + 40 < 55 which translates to- 10+40=50 becoming the new distance.
So, now the dist array is- [0, 10, 40, 50, 5]
And that’s how the iterations will continue until priority queue is empty.
Dijkstra's algorithm - Java Program
Class to create graph is written as a separate class. For creating adjacency list, Map storing List data structure is used.
Edge is defined as a static inner class which also implements comparable to keep edges in order of weights. That helps with creating a min heap.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Graph {
static class Edge implements Comparable<Edge>{
int destination;
int weight;
Edge(int destination, int weight){
this.destination = destination;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return Integer.compare(this.weight, o.weight);
}
}
int vertices;
Map<Integer, List<Edge>> adjList;
Graph(int vertices){
this.vertices = vertices;
adjList = new HashMap<>();
}
void addEdge(int source, int destination, int weight) {
adjList.computeIfAbsent(source, k->new ArrayList<>()).add(new Edge(destination, weight));
// For undirected graph
adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(new Edge(source, weight));
}
void printGraph() {
for(Map.Entry<Integer, List<Graph.Edge>> es :adjList.entrySet()) {
System.out.print("Vertex " + es.getKey() + " connects to: ");
List<Edge> list = es.getValue();
for (Edge e : list) {
System.out.print("[" + e.destination + " with weight " + e.weight + "] ");
}
System.out.println();
}
}
}
Dijkstra's algorithm Java implementation
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
public class Dijkstra {
public void dijkstra(int src, Graph graph) {
boolean[] visited = new boolean[graph.vertices];
int[] dist = new int[graph.vertices];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<Graph.Edge> pq = new PriorityQueue<Graph.Edge>();
pq.add(new Graph.Edge(src, 0));
while(!pq.isEmpty()) {
Graph.Edge current = pq.poll();
int n = current.destination;
if(visited[n])
continue;
visited[n] = true;
System.out.println(Arrays.toString(visited));
for(Graph.Edge next : graph.adjList.getOrDefault(n, Collections.emptyList())) {
int v = next.destination;
int w = next.weight;
System.out.println("Next " + v);
System.out.println("Distance " + w);
if(!visited[v] && dist[n] + w < dist[v]) {
dist[v] = dist[n] + w;
pq.add(new Graph.Edge(v, dist[v]));
}
}
System.out.println(Arrays.toString(dist));
}
printDistances(dist, src);
}
public void printDistances(int[] dist, int src) {
System.out.println("Shortest distances from vertex " + src + ":");
for(int i = 0; i < dist.length; i++) {
System.out.println("To vertex " + i + " -> " +dist[i]);
}
}
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 5);
graph.addEdge(1, 2, 30);
graph.addEdge(1, 3, 40);
graph.addEdge(3, 4, 50);
graph.printGraph();
Dijkstra d = new Dijkstra();
d.dijkstra(0, graph);
}
}
Output
Vertex 0 connects to: [1 with weight 10] [4 with weight 5] Vertex 1 connects to: [0 with weight 10] [2 with weight 30] [3 with weight 40] Vertex 2 connects to: [1 with weight 30] Vertex 3 connects to: [1 with weight 40] [4 with weight 50] Vertex 4 connects to: [0 with weight 5] [3 with weight 50] [true, false, false, false, false] Next 1 Distance 10 Next 4 Distance 5 [0, 10, 2147483647, 2147483647, 5] [true, false, false, false, true] Next 0 Distance 5 Next 3 Distance 50 [0, 10, 2147483647, 55, 5] [true, true, false, false, true] Next 0 Distance 10 Next 2 Distance 30 Next 3 Distance 40 [0, 10, 40, 50, 5] [true, true, true, false, true] Next 1 Distance 30 [0, 10, 40, 50, 5] [true, true, true, true, true] Next 1 Distance 40 Next 4 Distance 50 [0, 10, 40, 50, 5] Shortest distances from vertex 0: To vertex 0 -> 0 To vertex 1 -> 10 To vertex 2 -> 40 To vertex 3 -> 50 To vertex 4 -> 5
Time and Space complexity of Dijkstra's algorithm
When implemented using PriorityQueue in Java, time complexity of Dijkstra's algorithm is
O((V+E) logV)
If there are V vertices in the graph then each insertion in PriorityQueue takes log V time so time for V insertions is V log V.
Then we also need to update distance by going through the neighbours of each vertex. For that we again make an entry in PriorityQueue with the updated distance. For each vertex upto E edges may cause re-insertion in the queue. Which means E log V time.
Initially we also fill the distance array with infinity that also takes O(V) time for V vertices.
So total time is - O(V) + O(V log V) + O(E log V), resulting in O((V+E) logV) time complexity.
Auxiliary space requirement is-
One distance array- O(V)
One visited array- O(V)
PriorityQueue- O(V)
Adjacency list where Edges reachable from each vertex are stored- O(V + E)
So resultant space complexity after removing constant factors is-
O(V + E)
That's all for the topic Dijkstra's Algorithm Java Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
- AVL Tree Java Program - Insertion, Traversal, Search
- Weighted Graph Java Program
- Heap Sort Java Program
- Stable and Unstable Sorting Algorithms
- Java Program to Reverse a String In-place
- ConcurrentLinkedDeque in Java With Examples
- Java String Class With Method Examples
- Spring IoC Container Types – ApplicationContext and BeanFactory
No comments:
Post a Comment