//Performs the execution of Dijkstra's algorithm
import java.util.ArrayList;
import java.util.PriorityQueue;
public class Dijkstra {
/** Initialization of single source */
public PriorityQueue<Vertex> initSingleSource(ArrayList<Vertex> V) { //init single source
PriorityQueue<Vertex> Q = new PriorityQueue<Vertex>();// priority queue Q
for (Vertex u : V) {
Q.add(u); //inserting elements
}
return Q;
}
/** calculate the shortest path */
public void getShortestPath(ArrayList<Vertex> V) {
Vertex u;
PriorityQueue<Vertex> Q = initSingleSource(V);
while (!Q.isEmpty()) {
u = Q.poll(); //extract minimum
for (Edge e : u.getOutGoingEdges()) { //decrease key
Vertex v = e.getToNode();
if (v.getDistance() > u.getDistance() + e.getWeight()) { //relaxation
v.setDistance(u.getDistance() + e.getWeight());
v.getDistance();
}
v.setPrev(u); //set parent node
}
}
}
}