Java Program. use midwest.txt, mcities.txt, and connect.txt for this exercise

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

Write a program called ShortestDistances that: 1. Reads the list of cities into a string array using StdIn. readA11strings () 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. 2. Reads the list of major cittes into a string array using Stdin. readAllstrings(). 3. 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 nonnegative 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. 4. Reads in each connection from the connections data file, one line at a time, where each line contains the names of two citles. 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. 5. Prints a header line for the table to follow (see code below for printing this header). 6. 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: To print the header line, use code something like this: Stdout, printf("z20s", "*); for (String majorCity: majorCities) \{ Stdout.printf("\%-12s", majorCity); Stdout.println(); Print each numeric entry in the table formatted using the format string " . That's four spaces before the specitier and tive after. Grading rubric The program is worth 20 points. Code that doesn't compile or that complles and then crashes will be given 0 points. The 20 points will be allocated as follows: - Reading the data filles into arrays properly (2 points); - Building the symbol table correctly (3 points); - Building the graph correctly (5 points): - Having the correct logic in the outer loop (5 points): - Having the correct logic in the inner loop (S points)