Dijkstra Algorithm

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]