Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph.
Write a program to implement the Dijkstra Algorithm
Algorithm Explanation
![]() | Create the Vertex for each city and build the graph. |
![]() | Build the set which keep tracking the vertices with minimum distance. |
![]() | Assign the graph weight for each vertex and initialize with infinite value. The set does not have all the vertices. |
![]() | Iterate the set and take each vertex which is not there in the set with the minimum value. Update the distance of all the adjacent vertices of the current node. |
![]() | Print the minimum distance from the source to destination. |
Source Code
package com.dsacode.DataStructre.priorityqueue; import java.util.PriorityQueue; import java.util.List; import java.util.ArrayList; import java.util.Collections; class Vertex implements Comparable < Vertex > { public final String name; public Edge[] adjacencies; public double minDistance = Double.POSITIVE_INFINITY; public Vertex previous; public Vertex(String argName) { name = argName; } public String toString() { return name; } public int compareTo(Vertex other) { return Double.compare(minDistance, other.minDistance); } } class Edge{ public final Vertex target; public final double weight; public Edge(Vertex argTarget, double argWeight) { target = argTarget; weight = argWeight; } } public class DijkstraPriorityQueue { public static void computePaths(Vertex source) { source.minDistance = 0.; PriorityQueue < Vertex > vertexQueue = new PriorityQueue < Vertex >(); vertexQueue.add(source); while (!vertexQueue.isEmpty()) { Vertex u = vertexQueue.poll(); for (Edge e : u.adjacencies) { Vertex v = e.target; double weight = e.weight; double distanceThroughU = u.minDistance + weight; if (distanceThroughU < v.minDistance) { vertexQueue.remove(v); v.minDistance = distanceThroughU ; v.previous = u; vertexQueue.add(v); } } } } public static List < Vertex > getShortestPathTo(Vertex target) { List < Vertex > path = new ArrayList < Vertex >(); for (Vertex vertex = target; vertex != null; vertex = vertex.previous) path.add(vertex); Collections.reverse(path); return path; } public static void main(String[] args) { Vertex v0 = new Vertex("Mumbai"); Vertex v1 = new Vertex("Chennai"); Vertex v2 = new Vertex("Bangalore"); Vertex v3 = new Vertex("Hyderabad"); Vertex v4 = new Vertex("Coimbatore"); v0.adjacencies = new Edge[]{ new Edge(v1, 5), new Edge(v2, 10), new Edge(v3, 8) }; v1.adjacencies = new Edge[]{ new Edge(v0, 5), new Edge(v2, 3), new Edge(v4, 7) }; v2.adjacencies = new Edge[]{ new Edge(v0, 10), new Edge(v1, 3) }; v3.adjacencies = new Edge[]{ new Edge(v0, 8), new Edge(v4, 2) }; v4.adjacencies = new Edge[]{ new Edge(v1, 7), new Edge(v3, 2) }; Vertex[] vertices = { v0, v1, v2, v3, v4 }; computePaths(v0); for (Vertex v : vertices){ System.out.println("Distance to " + v + ": " + v.minDistance); List < Vertex > path = getShortestPathTo(v); System.out.println("Path: " + path); } } }
Output
Distance to Mumbai: 0.0 Path: [Mumbai] Distance to Chennai: 5.0 Path: [Mumbai, Chennai] Distance to Bangalore: 8.0 Path: [Mumbai, Chennai, Bangalore] Distance to Hyderabad: 8.0 Path: [Mumbai, Hyderabad] Distance to Coimbatore: 10.0 Path: [Mumbai, Hyderabad, Coimbatore]