Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. //Performs the execution of Dijkstra's algorithm
  2. import java.util.ArrayList;
  3. import java.util.PriorityQueue;
  4.  
  5. public class Dijkstra {
  6.    
  7.     /** Initialization of single source  */
  8.     public PriorityQueue<Vertex> initSingleSource(ArrayList<Vertex> V) { //init single source
  9.         PriorityQueue<Vertex> Q = new PriorityQueue<Vertex>();// priority queue Q
  10.         for (Vertex u : V) {
  11.             Q.add(u); //inserting elements
  12.         }
  13.         return Q;
  14.     }
  15.  
  16.     /** calculate the shortest path  */
  17.     public void getShortestPath(ArrayList<Vertex> V) {
  18.         Vertex u;
  19.         PriorityQueue<Vertex> Q = initSingleSource(V);
  20.        
  21.         while (!Q.isEmpty()) {
  22.             u = Q.poll(); //extract minimum
  23.             for (Edge e : u.getOutGoingEdges()) {  //decrease key
  24.                 Vertex v = e.getToNode();
  25.                 if (v.getDistance() > u.getDistance() + e.getWeight()) { //relaxation
  26.                     v.setDistance(u.getDistance() + e.getWeight());
  27.                     v.getDistance();
  28.                 }
  29.                 v.setPrev(u); //set parent node
  30.             }
  31.  
  32.         }
  33.     }
  34.  
  35. }