Given the definitions for vertices and graphs, create the classes and implement the Shortest Path algorithm as shown in the pseudo-code below. The most natural container for the Vertex ADT is your dynamic array (Lab0). The queue created on line #4 of the Shortest Path algorithm will need to be implemented if you haven't implemented a queue yet this quarter.  Specification: Create an Adjacency Matrix for the Airports.png file(image is posted above), and apply the Shortest Path algorithm. Use your dynamic array from lab0 to represent the Adjacency Matrix. If necessary create a queue class to support the Shortest Path algorithm. Vertex ADT T key container adjacent; bool visited int distance int ID AdjVertex ADT Vertex vertex int weight Graph ADT vertices Init() InsertVertex(value ) InsertEdge(startValue,endValue,weight) DeleteVertex(value) DeleteEdge(startValue,endValue) Search(value) Print() Algorithm ShortestPath(startValue) 1 vertex = search(startValue) 2 vertex.visited = true 3 vertex.distance = 0 4 queue = new queue() 5 queue.enqueue(vertex) 6 while (queue Not empty) 7 n = queue.dequeue() 8 for x = 0 to v.adjacent.end 9 if (Not n.adjacent[x].vertex.visited) 10 n.adjacent[x].vertex.distance = n.distance + 1 11 previous[adjacent[x].vertex.ID = n.ID 12 n.adjacent[x].vertex.visited = true 13 queue.enqueue(n.adjacent[x].vertex) This is my Lab 0 Dynamic array in c++: 

#include #include #include

using namespace std;

template class DynamicArray { private: /* Member Variables */ T* _array; int _numElements; int _capacity; T _ptemp; /* Member Functions */ // Constructor public: DynamicArray() { _capacity = 10; _numElements = 0; _array = new T[_capacity]; }

// Gets the current number of entries in container int getCurrentSize() { return _numElements; }

// Returns the current capacity of the container int capacity() { return _capacity; }

// Checks whether the container is empty. bool isEmpty() { return _numElements == 0; }

// Adds a new entry to the container bool insert(T newEntry) { if (_numElements == _capacity) { resize(); }

_array[_numElements] = newEntry; _numElements++;

return true; }

// Removes an entry from the container and moves all entries above anEntry down one bool remove(T anEntry) { int x = 0; while (_array[x] != anEntry) { x++; if (x == _numElements) { return false; } }

while (x

_numElements--; return true; }

// Get index value T getValue(int index) { return _array[index]; };

// Removes all entries from the container void clear() { delete _array; } // Resize a container by doubling current capacity int resize() { T* ptemp = new T[_capacity * 2]; for (int i = 0; i<_numelements i ptemp _array delete _capacity>

int main() {

std::string line; DynamicArray my_array;

std::ifstream myfile("words.txt"); if (myfile.is_open()) { while (std::getline(myfile, line)) { my_array.insert(line); } myfile.close();

my_array.remove("fallen"); for (int i = 0; i

else std::cout

my_array.clear();

return 0; }

Seattle 2661 Minne apolis 2161 1306 1483 1532 Denver Frandsco 19 Las 225 1258 Vegas 629 1983 Dallas 435 Angeles 61 Chicago 2113 16 1145 Boston 613 338 725 New York 83 Wash DC 2145 1709 Miami