JAVA Using the data files below:

Write a program called DISTSH that:

Reads the list of cities into a string array using StdIn.readAllStrings() and then 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.

Reads the list of major cities into a string array using StdIn.readAllStrings().

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 connections data file, one line at a time, where each line contains the names of two cities. As it reads in each line, it adds an edge to the graph. To do this, it will have to translate from the cities given on each connection line to their corresponding vertex numbers.

Prints a header line for the table to follow (see code below for printing this header).

For each city:

Creates a BreadthFirstPaths object with that city as the starting vertex

For each major city

Prints the shortest distance from the major city to the city in the outer loop

Here is an example of the first few lines of 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 To print the header line, use code something like this:

 StdOut.printf("%20s", "");

 for (String majorCity: majorCities) {

 StdOut.printf("%-12s", majorCity);

 }

 StdOut.println();

Print each numeric entry in the table formatted using the format string " %3d ". That's four spaces before the specifier and five after. Program SHOULD: Read the data files into arrays properly; build the symbol table correctly; build the graph correctly; have the correct logic in the outer loop; have the correct logic in the inner loop.

DATA Files:

midwest.txt: cities in the midwest

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

mcities.txt: major hubs cities

Chicago KansasCity Milwaukee Minneapolis SaintLouis

connect.txt: different conections between cities

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