Dijsktra

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author amit. 
 */
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Stack;
public class Dijsktra {
    
    private WeightedGraph myGraph;
    private int V;
     int [] parent;
     double [] distance;
    private boolean [] visited;
    
    
    
    public Dijsktra(WeightedGraph graph){
        this.myGraph = graph;
        this.V = graph.V;
        parent = new int [this.V];
        distance = new double [this.V];
        visited = new boolean[V];
    }
    
    public void initialize(int src){
        for(int i = 0; i < V; i++){
            if(i != src){
                distance[i] = Double.POSITIVE_INFINITY;
                visited[i] = false;
                parent[i] = -1;
            }
        }
        distance[src] = 0;
        parent[src] = src;
        visited[src] = false;
    }
    public boolean hasPath(int src, int destination){
        shortestDistance(src);
        boolean val = false;
        if(distance[destination]!= Double.POSITIVE_INFINITY)
            val = true;
        return val;
    }
    public Stack computePath(int src, int destination){
        if(!hasPath(src,destination)){
            System.out.println("noPath between specified vertices");
            return null;
        }
        Stack<Integer> myStack = new Stack<>();
        while( destination != src){
            myStack.add(destination);
            destination = parent[destination];
        }
        return myStack;
    }
    public void printPath(int src, int destination){
        Stack <Integer> myStack = computePath(src,destination);
        System.out.print("The path between vertices "+src +" and "+ destination+ "is : "+ src+" ");
        while(!myStack.empty()){
            System.out.print(myStack.pop()+" ");
        }
    }
    
    public void shortestDistance(int src){
        initialize(src);
        Vertex tmp = new Vertex(src,distance[src]);
        PriorityQueue<Vertex> minPQ = new PriorityQueue<>();
        minPQ.offer(tmp);
        while(!minPQ.isEmpty()){
            Vertex from = minPQ.poll();
            int x = from.vertexNumber;
            if(visited[x]) continue;
            for(WeightedEdge edge: myGraph.getNeighbours(x)){
                int y = edge.to();
                if(distance[y] > distance[x]+edge.weight){
                    distance[y] = distance[x]+edge.weight;
                    parent[y] = x;
                    minPQ.offer(new Vertex(y,distance[y]));
                }
            }
        }
    }
    
    private class Vertex implements Comparable<Vertex>{
        int vertexNumber;
        double distance;
        public Vertex(int x, double y){
            this.vertexNumber = x;
            this.distance = y;
        }
        

        @Override
        public int compareTo(Vertex that) {
            if(this.distance > that.distance){
                return 1;
            }
            else if(this.distance < that.distance){
                return -1;
            }
            else{
                return 0;
            }
            
        }
    }
    
    
    
}

WeightedEdge

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author amit
 * @param <E>
 */
public class WeightedEdge<E> implements Comparable <WeightedEdge>{
    int src_V;
    int des_V;
    double weight;
    E alpha;
    public WeightedEdge(int src, int des, double val){
        this.src_V = src;
        this.des_V = des;
        this.weight = val;
    }
    
    public WeightedEdge(int src, int des, E djd){
        this.src_V = src;
        this.des_V = des;
        this.alpha = djd;
    }
    public int from(){
        return this.src_V;
    }
    public int to(){
        return this.des_V;
    }
    public double cost(){
        return this.weight;
    }

    @Override
    public int compareTo(WeightedEdge that){
        if(this.weight < that.weight)
            return -1;
        else if(this.weight > that.weight)
            return 1;
        else
            return 0;
    }
    
    public WeightedEdge reverse(){
        WeightedEdge tmp = new WeightedEdge(this.des_V,this.src_V,this.weight);
        return tmp;
    }
}

WeightedGraph

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author amit
 */
//package Graphs;
import java.util.*;
public class WeightedGraph {
    int V;
    int E = 0;
    PriorityQueue<WeightedEdge> [] adjList;    
    // constructor
    public WeightedGraph(int numVertices){
        this.V = numVertices;
        adjList = (PriorityQueue<WeightedEdge>[])new PriorityQueue<?> [numVertices];
        for(int i = 0; i< V; i++){
            adjList[i] = new PriorityQueue<>();
        }
       // adjList = new PriorityQueue[V];
    }
    public  void addEdge(int src, int des, double val){
        WeightedEdge edge = new WeightedEdge(src,des,val);
        addEdge(edge);
    }
    
    private void addEdge(WeightedEdge edge){
        adjList[edge.src_V].offer(edge);
        adjList[edge.des_V].offer(edge.reverse());
    }
    public PriorityQueue<WeightedEdge> getNeighbours(int src){
        return adjList[src];
    }
    
    public void printNeighbours (int src){
        PriorityQueue<WeightedEdge> tmp = getNeighbours(src);
        System.out.print("The neighbours of vertex i are : ");
        for(WeightedEdge e: tmp){
            System.out.print(" "+e.des_V+ " with cost "+e.weight+ " ");
        }
    }
    
    public void printGraph(){
        for(int i = 0; i< V; i++){
            PriorityQueue<WeightedEdge> tmp = getNeighbours(i);
           // Iterator<PriorityQueue<WeightedEdge> in = tmp.iterator();
            System.out.print("Edges from vertex "+ i+" are  :");
            for(WeightedEdge e: tmp){
                System.out.print(" to destination "+e.des_V+" cost "+e.weight);
            }
            System.out.println("");
            
        }
    }
    
}