Instance variable types The programming component of this lab consists of implem
ID: 3725507 • Letter: I
Question
Instance variable types The programming component of this lab consists of implementing Dijkstra's algorithm by completing the run) and returnPath) methods of the ShortestPaths class, which can be found in the ShortestPaths.java file in the spath lab in your repository The ShortestPaths class contains instance variables of several important types. You will need to interact with these variables to implement your solution, and part of the challenge of this lab is understanding the types of these instance variables, how they are related, and how they interact via their methods. This is good practice for real-world coding, in which you will often be handed some already-existing eode infrastructure that you need to modify rather than gberating your entire project from scratch onself For cach of the following subecctions, answer the questions given. 1.1 Instance variable types Some of the important instance variable types you'll work with are: e Vertex Edge verte:And Dist Decreaser Map These types are defined either in their own classes in the spath or spath.graphs pacages, or in the Java standard documentation. Answer the following questions about these types 1. For a given Vertex object, what method call on that object would return all of its neighbors that ane relevant to running the main loop of Dijkstra's algorithm? 2. Which type of object will the min-heap priority queue used in our implementatioa of Dijkstra's Algo- rithm hold? 3. Which type of object is suitable for storing edge weights? How would an edge's weight be accessed using this object? 4. What method of the VertexAndDist class allows us to associate a new distance with a Vertex? 5. For a Decreaser object vDec, give a single Java code statement that would decrease method of the ShortestPaths class the distance associated with vDec to 247. (Hint: see the run for an example.)Explanation / Answer
(1) The returnPath() method would return a list of edges creating the shortest path from the given vertex to the end vertex.
(2) The minHeap or Priority queue will contain objects of type VertexandDist. It aggregates a vertex and its distance from a given source node, comparing all the distances.
(3) The edge weight could be stored as an Integer. The integer would be used in a hash map along with the destination node and the map can be accessed to calculate the distance between start and end nodes.
The definition of the HashMap will be as follows:
public HashMap<Vertex, Edge> toEdge;
(4) sameVertexNewDistance(int newdistance) allows reducing the distance to a given node.
(5) The code is as follows:
d.decrease(d.getValue().vDec(247));