For this assignment, you will implement Dijkstra's algorithm in order to determine the

cheapest flights from San Francisco to other cities for a fictitious airline, CS Airlines.

Consider the following map of available flights on CS Airlines. Each vertex has a name

and an index, e$.$g$.$ SFO has index $0,$ LAX has vertex $1,$ etc. Each edge has a weight which

is the cost of a ticket between the two cities.

We can represent this map as an adjacency matrix:

Design and implement a C$++$ class to represent this graph using an adjacency matrix. In

addition to storing the adjacency matrix, your class should include a method which uses

Dijkstra's algorithm in order to compute and print out the cheapest cost from San

Francisco $($vertex $0)$ to each other city. It may help you debug to print out the weight

array, $v,$ and vertex set for each iteration of the algorithm.

You do not need to provide methods for the standard graph operations, e$.$g$.$ to

add$/$remove vertices and edges. One interesting design choice is how to store your

vertex set. You may use any work you've done on previous assignments, e$.$g$.$ your List,

you may modify your List to fit this problem, or you may come up with your own

solution from scratch.

Submission

Submit your code base, and sample output printing out the lowest cost fares from San

Francisco to each city. You may use the numbers of the city vertex instead of the city

name if you would like.