Dijkstra's algorithm is outlined in pseudocode below:

• Set the distance of the source vertex to 0.
• For all vertices, except the source vertex, set distance to infinity.
• Create a priority queue, and add all vertices to it.
• While the queue is not empty ...
  • perform removeMin on the priority queue. u is the minimum vertex.
  • For all neighbors v of u ...
    • Check if dist[v] > dist[u] + cost(u,v)
    • If so, make dist[v] = d[u] + cost(u,v)
    • And also parent[v] = u.

Your program shall read a graph specification from the keyboard (just like in the first lab), ask for a source vertex, and perform Dijkstra's algorithm on the graph. Your program shall display:

• The length of the shortest path to every vertex.
• The shortest path to every vertex.

** need help with the Remove method, and the while loop. **

 

import java.util.Scanner;import java.util.Collection;import java.util.PriorityQueue;import java.util.Iterator;import java.util.Hashtable;public class DFSS {public static final double INFINITY = Double.POSITIVE_INFINITY;public static void main(String[] args) throws NoSuchVertexException {int number_of_verticies;// number of verticiesfinal int distance;// distance of verticiesVertex u;// minimum vertexPriorityQueue<Vertex> pq = new PriorityQueue<>(); // Create Priority QueueHashtable<String,Vertex> ht = new Hashtable<>(); // Create HashTableArrayDiGraph<String, Double, Integer> graph = new ArrayDiGraph<>();//Create ArrayDiGraphdistance = Integer.MAX_VALUE;// Set distance to INFINITY//Create ScannerScanner keyboard = new Scanner(System.in);System.out.println("Please input commands");while(true){String value = keyboard.nextLine();if(value.length() == 1) {graph.addVertex(value, null);// Add to hash tableht.put(value, new Vertex(value, INFINITY));}else if (value.length() == 3) {graph.addEdge(Character.toString(value.charAt(0)),Character.toString(value.charAt(1)),Character.getNumericValue(value.charAt(2)));}else {break;}}// removeMin methodVertex removeMin() {String minItem = node();pq[1] = pq[currentSize--];return minItem;}// Ask for the source vertexSystem.out.println("What's the source vertex?");String source = keyboard.nextLine();// Get the vertex called source from htVertex v = ht.get(source);v.distance = 0;// Add all vertices to queuepq.addAll(ht.values());