Find the shortest paths between nodes in a graph using Dijkstras algorithm

Dijkstras algorithm is an algorithm for finding the shortest paths between nodes in a graph. Dijkstra’s Algorithm solves the single-source shortest path problem in weighted graphs. It is similar to Prims algorithm. Dijkstra algorithm can be used for graphs with all positive weight edges only. Dijkstra is not lacks distribute property.

Write a program to implement Dijkstra’s algorithm

source Code

package com.dsacode.Algorithm.greedy;
 
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 EdgeDijkstra[] 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 EdgeDijkstra
{
    public final Vertex target;
    public final double weight;
    public EdgeDijkstra(Vertex argTarget, double argWeight){
     target = argTarget;
     weight = argWeight;
    }
}
 
public class Dijkstra
{
    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 (EdgeDijkstra 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("Delhi");
    Vertex v1 = new Vertex("Mumbai");
    Vertex v2 = new Vertex("chennai");
    Vertex v3 = new Vertex("Bangalore");
    Vertex v4 = new Vertex("Pune");
 
    v0.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v1, 5),
                                 new EdgeDijkstra(v2, 10),
                               new EdgeDijkstra(v3, 8) };
    v1.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v0, 5),
                                 new EdgeDijkstra(v2, 3),
                                 new EdgeDijkstra(v4, 7) };
    v2.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v0, 10),
                               new EdgeDijkstra(v1, 3) };
    v3.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v0, 8),
                                 new EdgeDijkstra(v4, 2) };
    v4.adjacencies = new EdgeDijkstra[]{ new EdgeDijkstra(v1, 7),
                               new EdgeDijkstra(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 Delhi: 0.0
Path: [Delhi]
Distance to Mumbai: 5.0
Path: [Delhi, Mumbai]
Distance to chennai: 8.0
Path: [Delhi, Mumbai, chennai]
Distance to Bangalore: 8.0
Path: [Delhi, Bangalore]
Distance to Pune: 10.0
Path: [Delhi, Bangalore, Pune]

Algorithm Explanation

	Initialize distance of each vertex from source as a positive infinitive, and distance back to source 0.
	Set the initial node as current. Mark all other nodes unvisited
	Find minimum distance vertex, which is not yet explored and put it to explored set.
	Find all vertices reachable from current vertex and update its distance if it is less than distance
	Repeat this process and print the shortest path between two vertices.

Reference

1. http://www3.cs.stonybrook.edu/~skiena/combinatorica/animations/dijkstra.html
2. https://en.wikipedia.org/?title=Dijkstra%27s_algorithm
3. http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html
4. http://mathworld.wolfram.com/DijkstrasAlgorithm.html
5. http://techieme.in/shortest-path-using-dijkstras-algorithm