Java question! Implement a breadth-first search algorithm to find a path from Bo
ID: 3804155 • Letter: J
Question
Java question!
Implement a breadth-first search algorithm to find a path from Boston to Minneapolis by using input.csv
input.csv:
The output is Boston-New York-?-?....-.-.-?-MINNEAPOLIS
Please help! Show code and explain!
STATE CODE ZIP CODE STATE ABBREVIATION NAME LATITUDE LONGITUDE 25 2108 MA BOSTON 71.06843 42.3576 36 10001 NY NEW YORK CITY 73.99671 40.74838 42 19102 PA PHILADELPHIA 75.16611 39.94891 24 21201 MD BALTIMORE 76.6252 39.29463 11 20001 DC WASHINGTON 77.01769 38.91222 37 28202 NC CHARLOTTE 80.84186 35.229 13 30303 GA ATLANTA 84.38885 33.7525 42 15112 PA PITTSBURGH 79.83889 40.40358 39 43201 OH COLUMBUS 83.00473 39.99516 18 46201 IN INDIANAPOLIS 86.10935 39.77501 29 63101 MO ST. LOUIS 90.19131 38.63462 29 64101 MO KANSAS CITY 94.60185 39.10005 8 80202 CO DENVER 104.9946 39.74911 40 73102 OK OKLAHOMA CITY 97.51993 35.4726 48 75201 TX DALLAS 96.80439 32.79044 48 77002 TX HOUSTON 95.35936 29.75937 22 70124 LA NEW ORLEANS 90.10938 30.00708 47 38103 TN MEMPHIS 90.048 35.144 13 30303 GA ATLANTA 84.38885 33.7525 12 32202 FL JACKSONVILLE 81.65167 30.32988 47 37201 TN NASHVILLE 86.77844 36.16703 17 60601 IL CHICAGO 87.61812 41.88585 27 55401 MN MINNEAPOLIS 93.26825 44.98347Explanation / Answer
package chegg;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class BFSDistanceMessaure {
public static void main(String[] args) {
List<City> cities = BFSDistanceMessaure.readFile(new File(
"d://Longitude-latitude.csv"));
List<CityWiseDistanceFromBoston> cityDistanceList = new ArrayList<CityWiseDistanceFromBoston>();
for (City city : cities) {
double distance = BFSDistanceMessaure.distanceCalculator(cities
.get(0).getLatitude(), cities.get(0).getLongitude(), city
.getLatitude(), city.getLongitude(), "K");
CityWiseDistanceFromBoston cityDistance = new CityWiseDistanceFromBoston(
city, distance);
System.out.println(cityDistance.toString());
cityDistanceList.add(cityDistance);
}
}
private static List<City> readFile(File fileName) {
List<City> cities = new ArrayList<City>();
try (BufferedReader br = new BufferedReader(new FileReader(fileName))) {
String sCurrentLine;
while ((sCurrentLine = br.readLine()) != null) {
City city = new City();
StringTokenizer strings = new StringTokenizer(sCurrentLine, ",");
int index = 0;
while (strings.hasMoreTokens()) {
if (CityEnum.ZIPCODE.getIndex() == index) {
city.setZipCode(Integer.parseInt(strings.nextToken()));
} else if (CityEnum.STATECODE.getIndex() == index) {
city.setStateCode(Integer.parseInt(strings.nextToken()));
} else if (CityEnum.STATEABERIVATION.getIndex() == index) {
city.setStateAberivation(strings.nextToken());
} else if (CityEnum.NAME.getIndex() == index) {
city.setName(strings.nextToken());
} else if (CityEnum.LATITUDE.getIndex() == index) {
city.setLatitude(Double.parseDouble(strings.nextToken()));
} else if (CityEnum.LONGITUDE.getIndex() == index) {
city.setLongitude(Double.parseDouble(strings
.nextToken()));
}
index++;
}
cities.add(city);
}
} catch (IOException e) {
e.printStackTrace();
}
return cities;
}
public static double distanceCalculator(double lat1, double lon1,
double lat2, double lon2, String unit) {
double theta = lon1 - lon2;
double dist = Math.sin(deg2rad(lat1)) * Math.sin(deg2rad(lat2))
+ Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2))
* Math.cos(deg2rad(theta));
dist = Math.acos(dist);
dist = rad2deg(dist);
dist = dist * 60 * 1.1515;
if (unit == "K") {
dist = dist * 1.609344;
} else if (unit == "N") {
dist = dist * 0.8684;
}
return (dist);
}
private static double rad2deg(double rad) {
return (rad * 180 / Math.PI);
}
private static double deg2rad(double deg) {
return (deg * Math.PI / 180.0);
}
}
class City {
private int stateCode;
private int zipCode;
private String stateAberivation;
private String name;
private double latitude;
private double Longitude;
// default constructor
public City() {
}
// parameterized constructor
public City(int stateCode, int zipCode, String stateAberivation,
String name, double latitude, double longitude) {
super();
this.stateCode = stateCode;
this.zipCode = zipCode;
this.stateAberivation = stateAberivation;
this.name = name;
this.latitude = latitude;
Longitude = longitude;
}
public int getStateCode() {
return stateCode;
}
public void setStateCode(int stateCode) {
this.stateCode = stateCode;
}
public int getZipCode() {
return zipCode;
}
public void setZipCode(int zipCode) {
this.zipCode = zipCode;
}
public String getStateAberivation() {
return stateAberivation;
}
public void setStateAberivation(String stateAberivation) {
this.stateAberivation = stateAberivation;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public double getLatitude() {
return latitude;
}
public void setLatitude(double latitude) {
this.latitude = latitude;
}
public double getLongitude() {
return Longitude;
}
public void setLongitude(double longitude) {
Longitude = longitude;
}
@Override
public String toString() {
return "City [name=" + name + "]";
}
}
class CityWiseDistanceFromBoston {
private City city;
private double distance;
public CityWiseDistanceFromBoston(City city, double distance) {
super();
this.city = city;
this.distance = distance;
}
public City getCity() {
return city;
}
public void setCity(City city) {
this.city = city;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
@Override
public String toString() {
return "CityWiseDistanceFromBoston [city=" + city + ", distance="
+ distance + "]";
}
}
enum CityEnum {
STATECODE(0, "STATECODE"), ZIPCODE(1, "ZIPCODE"), STATEABERIVATION(2,
"STATEABERIVATION"), NAME(3, "NAME"), LATITUDE(4, "LATITUDE"), LONGITUDE(
5, "LONGITUDE");
private int index = 0;
private String value = null;
CityEnum(int index, String value) {
this.index = index;
this.value = value;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
}
class BFSAlgoritum {
private Queue<Integer> queue;
public BFSAlgoritum() {
queue = new LinkedList<Integer>();
}
public void bfs(int nearestNode[][], int source) {
int number_of_nodes = nearestNode[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
queue.add(source);
while (!queue.isEmpty()) {
element = queue.remove();
i = element;
System.out.print(i + " ");
while (i <= number_of_nodes) {
if (nearestNode[element][i] == 1 && visited[i] == 0) {
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.