Table of Contents
If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
In this post, we will see Dijkstra algorithm for find shortest path from source to all other vertices.
Problem
You will be given graph with weight for each edge,source vertex and you need to find minimum distance from source vertex to rest of the vertices.
Algorithm
There will be two core classes, we are going to use for Dijkstra algorithm.
Vertex: This class contains name, visited flag, predecessor(To track the short path, so that we can backtrack) and distance from source node and also the list of outgoing edge from this vertex.
Edge: This class contains Source vertex, target vertex, and weight.
Let’s first understand how are we going to solve it visually.
As you can see, we have initialized predecessor and minimum distance to default.Green node represents visited nodes and red color represent neighbors of the vertex.
Here we are considering :
Total distance from source vertex A to vertex B via vertex C: 15
Total distance from source vertex A to vertex D via vertex C: 19
Total distance from source vertex A to vertex E via vertex C: 21
As distance from C to B is minimum i.e 15, that’s why we have chosen vertex B as next vertex.
As you can see, we are done with Dijkstra algorithm and got minimum distances from Source Vertex A to rest of the vertices.
Let me go through core algorithm for Dijkstra.
- Set distance for source Vertex to 0.
- Set distance for all other vertices to infinity.
- At each vertex, we need to choose a node with minimum distance from source vertex and we are going to use priority queue for that.
- Add source node to PriorityQueue.
- Do the following when PriorityQueue is not empty
- Poll vertex (Let’ say vertex A) from the PriorityQueue.
- Iterate over neighbours(Let’s say Vertex B) for the vertex A.
- Calculate new distance for vertex B by adding vertex.getDistance and edge.getWeight
- If new distance < Vertex B’s current distance then update the node(Distance,predecessor) in PriorityQueue.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public void computeShortestPaths(Vertex sourceVertex){ sourceVertex.setDistance(0); PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>(); priorityQueue.add(sourceVertex); sourceVertex.setVisited(true); while( !priorityQueue.isEmpty() ){ // Getting the minimum distance vertex from priority queue Vertex actualVertex = priorityQueue.poll(); for(Edge edge : actualVertex.getAdjacenciesList()){ Vertex v = edge.getTargetVertex(); if(!v.isVisited()) { double newDistance = actualVertex.getDistance() + edge.getWeight(); if( newDistance < v.getDistance() ){ priorityQueue.remove(v); v.setDistance(newDistance); v.setPredecessor(actualVertex); priorityQueue.add(v); } } } actualVertex.setVisited(true); } } |
Let’s see complete source code for Dijkstra’s algorithm
Dijkstra’s algorithm example
Create a class named Vertex.java as below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
package org.arpit.java2blog.algo; import java.util.ArrayList; import java.util.List; public class Vertex implements Comparable<Vertex> { private String name; private List<Edge> adjacenciesList; private boolean visited; private Vertex predecessor; private double distance = Double.MAX_VALUE; public Vertex(String name) { this.name = name; this.adjacenciesList = new ArrayList<>(); } public void addNeighbour(Edge edge) { this.adjacenciesList.add(edge); } public String getName() { return name; } public void setName(String name) { this.name = name; } public List<Edge> getAdjacenciesList() { return adjacenciesList; } public void setAdjacenciesList(List<Edge> adjacenciesList) { this.adjacenciesList = adjacenciesList; } public boolean isVisited() { return visited; } public void setVisited(boolean visited) { this.visited = visited; } public Vertex getPredecessor() { return predecessor; } public void setPredecessor(Vertex predecessor) { this.predecessor = predecessor; } public double getDistance() { return distance; } public void setDistance(double distance) { this.distance = distance; } @Override public String toString() { return this.name; } @Override public int compareTo(Vertex otherVertex) { return Double.compare(this.distance, otherVertex.getDistance()); } } |
Create another class named Edge.java as below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
package org.arpit.java2blog.algo; public class Edge { private double weight; private Vertex startVertex; private Vertex targetVertex; public Edge(double weight, Vertex startVertex, Vertex targetVertex) { this.weight = weight; this.startVertex = startVertex; this.targetVertex = targetVertex; } public double getWeight() { return weight; } public void setWeight(double weight) { this.weight = weight; } public Vertex getStartVertex() { return startVertex; } public void setStartVertex(Vertex startVertex) { this.startVertex = startVertex; } public Vertex getTargetVertex() { return targetVertex; } public void setTargetVertex(Vertex targetVertex) { this.targetVertex = targetVertex; } } |
Create another class named "DijkstraShortestPath.java" as below. This will contain main Dijkstra algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
package org.arpit.java2blog.algo; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.PriorityQueue; public class DijkstraShortestPath { public void computeShortestPaths(Vertex sourceVertex){ sourceVertex.setDistance(0); PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>(); priorityQueue.add(sourceVertex); sourceVertex.setVisited(true); while( !priorityQueue.isEmpty() ){ // Getting the minimum distance vertex from priority queue Vertex actualVertex = priorityQueue.poll(); for(Edge edge : actualVertex.getAdjacenciesList()){ Vertex v = edge.getTargetVertex(); if(!v.isVisited()) { double newDistance = actualVertex.getDistance() + edge.getWeight(); if( newDistance < v.getDistance() ){ priorityQueue.remove(v); v.setDistance(newDistance); v.setPredecessor(actualVertex); priorityQueue.add(v); } } } actualVertex.setVisited(true); } } public List<Vertex> getShortestPathTo(Vertex targetVertex){ List<Vertex> path = new ArrayList<>(); for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){ path.add(vertex); } Collections.reverse(path); return path; } } |
Create another class named "DijkstraMain.java". This class will contain main function to run the algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
package org.arpit.java2blog.algo; public class DijkstraMain { public static void main(String[] args) { Vertex vertexA = new Vertex("A"); Vertex vertexB = new Vertex("B"); Vertex vertexC = new Vertex("C"); Vertex vertexD = new Vertex("D"); Vertex vertexE = new Vertex("E"); vertexA.addNeighbour(new Edge(10,vertexA,vertexC)); vertexA.addNeighbour(new Edge(17,vertexA,vertexB)); vertexC.addNeighbour(new Edge(5,vertexC,vertexB)); vertexC.addNeighbour(new Edge(9,vertexC,vertexD)); vertexC.addNeighbour(new Edge(11,vertexC,vertexE)); vertexB.addNeighbour(new Edge(1,vertexB,vertexD)); vertexD.addNeighbour(new Edge(6,vertexD,vertexE)); DijkstraShortestPath shortestPath = new DijkstraShortestPath(); shortestPath.computeShortestPaths(vertexA); System.out.println("======================================"); System.out.println("Calculating minimum distance"); System.out.println("======================================"); System.out.println("Minimum distance from A to B: "+vertexB.getDistance()); System.out.println("Minimum distance from A to C: "+vertexC.getDistance()); System.out.println("Minimum distance from A to D: "+vertexD.getDistance()); System.out.println("Minimum distance from A to E: "+vertexE.getDistance()); System.out.println("===================== ================="); System.out.println("Calculating Paths"); System.out.println("======================================"); System.out.println("Shortest Path from A to B: "+shortestPath.getShortestPathTo(vertexB)); System.out.println("Shortest Path from A to C: "+shortestPath.getShortestPathTo(vertexC)); System.out.println("Shortest Path from A to D: "+shortestPath.getShortestPathTo(vertexD)); System.out.println("Shortest Path from A to E: "+shortestPath.getShortestPathTo(vertexE)); } } |
When you run above program, you will get below output:
Calculating minimum distance
======================================
Minimum distance from A to B: 15.0
Minimum distance from A to C: 10.0
Minimum distance from A to D: 16.0
Minimum distance from A to E: 21.0
===================== =================
Calculating Paths
======================================
Shortest Path from A to B: [A, C, B] Shortest Path from A to C: [A, C] Shortest Path from A to D: [A, C, B, D] Shortest Path from A to E: [A, C, E]
That’s all about Dijkstra algorithm in java.
there a plenty examples for the Dijkstra’s algorithm in Java but this one is really good, clean and well explained. Thank you, Sir.