Language is C++

This is a weighted graph where the vertices represent cities and the edges indicate the Air Busters Airlines flights that connect the cities. The weights attached to the edges represent the air distances between the pairs of cities. Here is an array-based implementation that will find the shortest path from Washington to Chicago. Complete the implementation such that the user can enter a city from which they are leaving and a city they want to arrive in and the program will display the shortest path possible showing the cities along the way.

Weighted Graph

The implimtation:

template // Assumption: VertexType is a type for which the "=", // "==", and "&); void ClearMarks(); void MarkVertex(VertexType); bool IsMarked(VertexType); private: int numVertices; int maxVertices; VertexType* vertices; int edges[50][50]; bool* marks; // marks[i] is the mark for vertices[i]. };

template GraphType::GraphType() // Post: Arrays of size 50 are dynamically allocated for // marks and vertices. numVertices is set to 0; // maxVertices is set to 50. { numVertices = 0; maxVertices = 50; vertices = new VertexType[50]; marks = new bool[50]; }

template GraphType::GraphType(int maxV) // Post: Arrays of size maxV are dynamically allocated for // marks and vertices. // numVertices is set to 0; maxVertices is set to maxV. { numVertices = 0; maxVertices = maxV; vertices = new VertexType[maxV]; marks = new bool[maxV]; } template GraphType::~GraphType() // Post: Arrays for vertices and marks have been deallocated. { delete [] vertices; delete [] marks; }

const int NULL_EDGE = 0;

template void GraphType::AddVertex(VertexType vertex) // Post: vertex has been stored in vertices. // Corresponding row and column of edges have been set // to NULL_EDGE. // numVertices has been incremented. { vertices[numVertices] = vertex; for (int index = 0; index

template int IndexIs(VertexType* vertices, VertexType vertex) // Post: Returns the index of vertex in vertices. { int index = 0;

while (!(vertex == vertices[index])) index++; return index; }

template void GraphType::AddEdge(VertexType fromVertex, VertexType toVertex, int weight) // Post: Edge (fromVertex, toVertex) is stored in edges. { int row; int col;

row = IndexIs(vertices, fromVertex); col = IndexIs(vertices, toVertex); edges[row][col] = weight; }

template int GraphType::GetWeight (VertexType fromVertex, VertexType toVertex) // Post: Returns the weight associated with the edge // (fromVertex, toVertex). { int row; int col;

row = IndexIs(vertices, fromVertex); col = IndexIs(vertices, toVertex); return edges[row][col]; }

template void GraphType::GetToVertices(VertexType vertex, QueType& adjVertices) // Post: Returns a queue of vertices adjacent from vertex. { int fromIndex; int toIndex;

fromIndex = IndexIs(vertices, vertex); for (toIndex = 0; toIndex Dallas 1300 Washington Austin 1400 Denver Atlanta Houston Chicago Dallas 1300 Washington Austin 1400 Denver Atlanta Houston Chicago