In this assignment, you are given two data files:

a6cities.txt: List of midwestern cities

a6connections.txt: List of direct connections between those cities

Download and place both of those files into the Eclipse data directory.

Create a package called assignment6. In it, write a program called ShortestDistances that:

Reads in the list of cities and builds a symbol table where the key is the name of a city and the value is an integer from 0 to the number of cities minus one. The first city gets 0, the second gets 1, and so forth.

Creates an empty undirected graph using the class algs41.Graph. In this graph, each vertex represents a city. As we discussed, the vertices of an undirected graph are labelled with non-negative integers. When the vertices represent real world objects, this makes it difficult to connect a vertex's integer label with its real world label. You will use the symbol table just constructed to make this connection.

Reads in each connection from the second data file, one line at a time. As it reads in each line, it adds an edge to the graph. It will have to translate from the cities given on each connection line to their corresponding vertex numbers.

Creates a algs41.BreadthFirstPaths object from the graph just constructed and with Chicago as the starting point.

Using the BFS object, prints a two-dimensional table listing the shortest distances (by way of Chicago) between each pair of cities in the following list:

Chicago

KansasCity

Minneapolis

Wausau

LaCrosse

Here is an example of the expected output:

 Chicago KansasCity Minneapolis Wausau LaCrosse Chicago 0 5 4 3 3 KansasCity 5 10 9 8 8 Minneapolis 4 9 8 7 7 Wausau 3 8 7 6 6 LaCrosse 3 8 7 6 6 

a6cities.txt

Alton Appleton Carbondale Carlinville Centralia Champaign-Urbana Chicago Galesburg JeffersonCity Joliet Kankakee KansasCity Kewanee LaCrosse LaPlata Mattoon Milwaukee Minneapolis Naperville Oshkosh Pontiac Portage Quincy RedWing SaintLouis Springfield Wausau Wittenburg

a6connections.txt

Alton SaintLouis Appleton Wausau Appleton Wittenburg Carlinville Alton Centralia Carbondale Champaign-Urbana Mattoon Chicago Joliet Chicago Kankakee Chicago Milwaukee Chicago Naperville Galesburg LaPlata Galesburg Quincy JeffersonCity KansasCity Joliet Pontiac Kankakee Champaign-Urbana Kewanee Galesburg LaCrosse RedWing LaPlata KansasCity Mattoon Centralia Milwaukee Oshkosh Milwaukee Portage Milwaukee Wittenburg Naperville Kewanee Oshkosh Appleton Pontiac Springfield Portage LaCrosse RedWing Minneapolis SaintLouis JeffersonCity Springfield Carlinville Wausau Minneapolis Wittenburg Wausau