import java.util.Arrays;

import java.util.Comparator;

import java.util.PriorityQueue;

import java.util.List;

public class ShortestPath {

public int weightOfShortestPath(Graph graph, int start, int end)

{

int distanceArray[]=new int[graph.getNodes().size()];

//set distance of all nodes as infinite i.e max_value

for(int i=0; i<distanceArray.length; i++)

distanceArray[i]=Integer.MAX_VALUE;

distanceArray[start]=0;//set distance of source as 0

//a comparator to

Comparator<Integer> cmp=new Comparator<Integer>()

{

public int compare(Integer a, Integer b)

{

if(distanceArray[a]<distanceArray[b])

return -1;

else if(distanceArray[a]==distanceArray[b])

return 0;

else

return 1;

}

};

//priority queue to get the minimum weight node from source

PriorityQueue<Integer> pq=new PriorityQueue<Integer>(cmp);//min heap

for(int i=0; i<distanceArray.length; i++)

pq.add(i);//add all the nodes to the priority queue

while(!pq.isEmpty())

{//while the priority queue is not empty

int node=pq.remove();

List<Edge> list=graph.getOutgoingEdges(node);//get all the outgoing edges from the node

for(Edge edge: list)

{//traverse over all edges

if(pq.contains(edge.getTo()))

{//if edge head is present in the priority queue

if(distanceArray[node]+edge.getWeight()<distanceArray[edge.getTo()])

{//check distance, if less than update the old distance to new distance

distanceArray[edge.getTo()]=distanceArray[node]+edge.getWeight();

}

//update the priority queue

pq.remove(edge.getTo());

pq.add(edge.getTo());

}

}

}

//print the minimum distance to all nodes from the start node

System.out.println("Minimum distance to all nodes from source is: "+Arrays.toString(distanceArray));

return distanceArray[end];//return the minimum distance from start to end node

}

public static void main(String ar[])

{

int matrix[][]= {

{0, 3, 5, 0, 0, 0},

{0, 0, 1, 1, 0, 0},

{0, 0, 0, 2, 0, 0},

{0, 0, 0, 0, 1, 3},

{0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 1, 0}

};

Graph graph=new Graph(matrix);

//get minimum distance from 0th node to 5th node

ShortestPath sp=new ShortestPath();

int dis=sp.weightOfShortestPath(graph, 0, 5);

System.out.println("The minimum distance from 0th node to 5th node is: "+dis);

}

}