Description
Assignment Goals
The goal of this project is to:
1. Familiarize students with **graphs**
2. Allow students a chance to **choose** their data structure storage method
Program
Overview
**The Traveling Salesman Problem**
Consider 5 cities of interest:
1. Reno
2. San Francisco
3. Salt Lake City
4. Seattle
5. Las Vegas
Use information on available maps to determine the distance (in miles) from one city to the other. Assume a fixed fuel efficiency metric of 40 mps (miles per gallon) and derive the cost of each transition *in terms of gas*.
Requirements
Solve the Traveling Salesman Problem such that traveling salesman starts from Reno, visits all cities in the above list and returns to Reno. Solve this problem in the brute force-way, i.e. by identifying all possible paths. Use a graph (with each of its vertices corresponding to one of these cities and its edges being weighted by the associated miles for each trip) to determine the cost of each path.
**Note:** if (and only if) to go from city A to B you must go through C then you must add one edge from A to C and one edge from C to B and there is no need to add an edge directly from A to B.
Deliverables
The Graph Interface has already been provided for you in this repository. Your submission should include
– Your source code
– a *modular* main driver
– the **complete** implementation for your Graph Class
– any additional class implementationns (including other data structures)
– a .txt file with your initial values for the miles from one city to the other
– a .txt file which includes all possible paths and the best one selected by the algorithm
Submission details
If you are usinng git from the command line, execute the following commands:
1. After accepting the assignment invitation, copy the clone URL
2. Type
“`git clone clone URL“`
3. cd into your new assignment directory
4. After working on your files
5. When you’re ready, type the following commands:
“`
git add .
git commit -m “your commit message”
git push
“`
