In this assignment, you will write a program to use Dijkstra's Algorithm to solve the single source shortest path problem:

Read a directed weighted graph G from an input file

Here is a small graph.

textfile of small graph:

10 4 8 4 10 6 9 6 74 10 4 7 7 1 7 6 2 6 7 2 96 9 5 1 9 3 6 2 1 74 5 8 8 5 3 4 10 5 3 7 8 1 7 64 6 3 5 2 7 43 5 100 1 5 10 4 6 9 5

The first line of the file contains n, the number of vertices of G. The names of the vertices are the integers from 1 to n.

Each remaining line of the graph is a list of integers separated by spaces, and represents the list of outneighbors of one vertex.

The first number in the line is the name of the vertex.

After that, there is a sequence of pairs, consisting of a vertex name and a weight.

The source will be vertex 1.

You are to print a shortest path from the source to each other vertex.

Here is a sample output if the input is the small graph.

There will be no more than 1000 vertices in the graph.

A larger graph.

II. Implementation of Priority Queue: Since we have not covered the Heap data structure in our course, it is not fair to require all of you implement minHeap as the priority queue. Therefore, you are only required to do a simple priority queue implementation based on an unsorted array list. I have provided you the code template, as well as the necessary code of Java ArrayList class (including other classes and interfaces), and you are not allowed to use any other Priority Queue implementation (such as the code online) that is not written by yourself. You are not allowed to use Java ArralyList library either. However, you can feel free to revise the provided ArrayList code for completing this assignment.

public class PQEntry { // the data element private Integer id; // the vertex id private Integer value; // the shortest distance to the source node private Boolean visited; // whether or not this vertex is visited private Integer prev; // the previous vertex leads to the source // your implementation // ... } public interface PQueue { int size(); boolean isEmpty(); PQEntry insert(PQEntry item); PQEntry min(); PQEntry removeMin(); } public class UnsortedPQueue implements PQueue { private List list = new ArrayList(); public int size() { // your code ... } public boolean isEmpty() { // your code ... } private int findMin() { // find the item with highest priority // return the corresponding position ID // your code ... } public PQEntry insert(PQEntry item) { // your code ... } public PQEntry min() { // your code ... } public PQEntry removeMin() { // your code ... } } public interface List{ public int size(); public boolean isEmpty(); public Object get(int index) throws OutOfRangeException; public void set(int index, Object o) throws OutOfRangeException; public void add(int index, Object o) throws OutOfRangeException; public Object remove(int index) throws OutOfRangeException; } public class ArrayList implements List{ private int CAP; private int size; private Object[] elements; public ArrayList(){ this(100); } public ArrayList(int capacity){ this.size = 0; this.CAP = capacity; this.elements = new Object[capacity]; } //Returns the size of the ArrayList public int size(){ return size; } //Returns if the ArrayList is storing Objects public boolean isEmpty(){ return size == 0; } //Returns the Object in the ArrayList at a given index public Object get(int index) throws OutOfRangeException{ if(index < size) return elements[index]; else throw new OutOfRangeException(); } //Sets the Object in the ArrayList at a given index public void set(int index, Object o) throws OutOfRangeException{ if (index < size) elements[index] = o; else throw new OutOfRangeException(); } //Adds a given Object to the ArrayList at a given index public void add(int index, Object o) throws OutOfRangeException{ if (index > size) throw new OutOfRangeException(); for(int i = size - 1; i >= index; i--){ elements[i+1] = elements[i]; } elements[index] = o; size++; } //Removes the Object in the ArrayList at a given index public Object remove(int index) throws OutOfRangeException{ if (index >= size) throw new OutOfRangeException(); Object o = elements[index]; for(int i = index; i < size - 1; i++){ elements[i] = elements[i+1]; } elements[size-1] = null; size--; return o; } } public class OutOfRangeException extends Exception{ public OutOfRangeException(){ System.out.println("Error: Boundary Out of Range"); } public OutOfRangeException(String str){ System.out.println(str); } }

Sample Output:

10 1 2 6 7 6 2 1 5 5 100 7 43 3 5 8 1 74 6 2 4 10 6 8 4 5 7 64 8 1 3 7 6 3 5 7 1 9 9 5 2 96 8 4 10 5 3 9 7 7 10 4 6 74 10 9 5 4 6 Inserting 1 Deleting 1 Inserting 2 Inserting 7 Deleting 2 Inserting 5 Deleting 7 Inserting 9 Deleting 9 Inserting 10 Inserting 6 Deleting 10 Inserting 4 Deleting 4 Inserting 8 Deleting 8 Updating the value of 5 in the queue Deleting 5 Inserting 3 Deleting 3 Updating the value of 6 in the queue Deleting 6 Shortest path to 1: 1: cost = 0 Shortest path to 2: 1 2: cost = 6 Shortest path to 3: 1 7 9 10 4 8 5 3: cost = 35 Shortest path to 4: 1 7 9 10 4: cost = 21 Shortest path to 5: 1 7 9 10 4 8 5: cost = 28 Shortest path to 6: 1 7 9 10 4 8 5 3 6: cost = 37 Shortest path to 7: 1 7: cost = 6 Shortest path to 8: 1 7 9 10 4 8: cost = 25 Shortest path to 9: 1 7 9: cost = 11 Shortest path to 10: 1 7 9 10: cost = 15