Hello, i am havign issues using a Dijkstra\'s algorithm and having it correctly
ID: 3838484 • Letter: H
Question
Hello, i am havign issues using a Dijkstra's algorithm and having it correctly link parents from destination to starting point. Half of our results are working correctly as expected and the other have are not. I have no idea why it is not doing this thing correctly in some cases.
Here is the code that i currently have for the whole project at least within my main file
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
public static void Dikstras(Vertice[] vertices, Vertice src){
Vertice name = null;
int weight = 0;
boolean check = false;
int edgeWeight = 0;
Edge edge = null;
src.setVisited(true);
for(int x = 0; x < src.getConnectedEdgesNum(); x++){
if(src.getEdge(x).getName1().getName().equals(src.getName())){
name = src.getEdge(x).getName2();
}
if(src.getEdge(x).getName2().getName().equals(src.getName())){
name = src.getEdge(x).getName1();
}
for(int y = 0; y < vertices.length; y++){
edgeWeight = src.getEdge(x).getWeight();
weight = src.getEdge(x).getWeight() + src.getValue();
check = name.getName().equals(vertices[y].getName());
if (check){
if(vertices[y].getName().equals("Seattle")){
int r = 0;
r = 20;
}
if(vertices[y].getValue() > weight){
vertices[y].setValue(weight);
vertices[y].setParent(src);
}
break;
}
}
}
for(int y = 0; y < src.getConnectedVerticeNum(); y++){
for(int z = 0; z < vertices.length; z++){
if (src.getVertices()[y].getName().equals(vertices[z].getName())){
name = vertices[z];
break;
}
}
if(name.getVisited() == false){
Dikstras(vertices, name);
}
}
}
public static void reset(Vertice[] vertices){
for(int x = 0; x < vertices.length; x++){
vertices[x].setVisited(false);
vertices[x].setParent(null);
vertices[x].setValue(Integer.MAX_VALUE);
}
}
/*
*
* //This is the Weight DFS
*
*/
public static void DFS(Vertice[] towns, Vertice town, Edge[] roads, Weight weight){
System.out.println("This is the towns traversed through DFS: "+ town.getName());
town.setVisited(true);
town.setValue(weight.getWeight());
for(int x = 0; x < town.getConnectedVerticeNum(); x++){
String name = town.getEdge(x).getName(town).getName();
Vertice newTown = findTown(name, towns);
int newTownWeight = town.getEdge(x).getWeight();
/* not needed at this point
if(newTown.getVisited() == true){
setBackEdge(town.getEdge(x));
}
*/
if(newTown.getVisited() == false){
setDiscoveryEdge(town.getEdge(x), roads);
weight.addWeight(newTownWeight);
DFS(towns, newTown, roads, weight);
}
}
}
/*
*
* Finds the specified town
*
*/
public static Vertice findTown(String name, Vertice[] towns){
Vertice town = null;
for(int x = 0; x < towns.length; x++){
if(towns[x].getName().equals(name)){
town = towns[x];
}
}
return town;
}
/*
*
*/
public static void findBackEdge(Edge[] roads, Edge[] backEdge){
int counter = 0;
for(int x = 0; x < roads.length; x++){
if(roads[x].getDiscoverEdge() == false){
backEdge[counter] = roads[x];
counter++;
}
}
}
/*
*
*
* This is where I set the Discovery edges within the DFS
*
*
*/
public static void setDiscoveryEdge(Edge road, Edge[] roads){
int whileCheck = 0;
for(whileCheck = 0; whileCheck < roads.length; whileCheck++){
if(roads[whileCheck].equals(road)){
roads[whileCheck].setDiscoveryEdge();
return;
}
}
}
/*
*
*
* I use this to find grand forks within the vertices list and then grab it and start using it
*
*
*/
public static Vertice getGrandForks(Vertice[] towns){
Vertice town = null;
for(int x = 0; x < towns.length; x++){
if(towns[x].getName().equals("Grand Forks")){
town = towns[x];
return town;
}
}
return town;
}
/*
*
*
* This is where i do most of the where, reading the file and generating the lists for the towns
* and for the roads on the map
*
*/
public static void readFile(Vertice[] towns, Edge[] roads, BufferedReader reader) throws NumberFormatException, IOException{
String line = null;
String[] tokens = new String[3];
int edgeValue = 0;
Vertice first = null;
Vertice second = null;
Edge edge = null;
while((line = reader.readLine()) != null){
tokens = line.split("//");
//System.out.println(tokens[0] + " " + tokens[1]+ " " + tokens[2]);
edgeValue = Integer.parseInt(tokens[2]);
first = new Vertice(tokens[0]);
second = new Vertice(tokens[1]);
edge = new Edge(first, second, edgeValue);
//Add road to the list
boolean check = false;
for(int x = 0; x < roads.length; x++){
if(roads[x] == null){
roads[x] = edge;
}
if(roads[x].getName1().equals(edge.getName1()) || roads[x].getName1().equals(edge.getName2())){
if(roads[x].getName2().equals(edge.getName2()) || roads[x].getName1().equals(edge.getName2())){
check = true;
break;
}
}
}
//iterate through until you hit a null to add at that location
if(check == false){
for(int x = 0; x < roads.length; x++){
if(roads[x] == null){
roads[x] = edge;
}
}
}
//Add towns to list
check = false;
boolean check1 = false;
int numStore = 0;
int numStore1 = 0;
for(int x = 0; x < towns.length; x++){
if(towns[x] == null){
break;
}
if(towns[x].getName().equals(tokens[0])){
check = true;
numStore = x;
first = towns[x];
}
if(towns[x].getName().equals(tokens[1])){
check1 = true;
numStore1 = x;
second = towns[x];
}
if(check == true && check1 == true){
break;
}
}
if(check == false){
for(int x = 0; x < towns.length; x++){
if(towns[x] == null){
towns[x] = first;
numStore = x;
towns[x].addEdge(edge);
break;
}
}
}else{
towns[numStore].addVerticie(second);
towns[numStore].addEdge(edge);
}
if(check1 == false){
for(int x = 0; x < towns.length; x++){
if(towns[x] == null){
towns[x] = second;
numStore1 = x;
towns[x].addEdge(edge);
break;
}
}
}else{
towns[numStore1].addVerticie(first);
towns[numStore1].addEdge(edge);
}
if(check == false){
towns[numStore].addVerticie(second);
}
if(check1 == false){
towns[numStore1].addVerticie(first);
}
}
}
public static void printParents(Vertice[] vertices, String stringName){
Vertice name = null;
Vertice parent = null;
String parentName = "";
for(int x = 0; x < vertices.length; x++){
if(vertices[x].getName().equals(stringName)){
name = null;
name = vertices[x];
while(name != null){
if(name.getParent() == null){
break;
}
System.out.println("this is the route to from destination to start: " + name.getName() + " --- To --- " + name.getParent().getName());
parent = name.getParent();
parentName = parent.getName();
for(int y = 0; y < vertices.length; y++){
if(parentName.equals(vertices[y].getName())){
name = vertices[y];
}
}
}
}
}
}
public static Vertice findVertice(Vertice[] vertices, String name){
Vertice node = null;
for(int x =0; x < vertices.length; x++){
if(vertices[x].getName().equals(name)){
node = vertices[x];
}
}
return node;
}
/*
*
*
* This is the main function
*
*
*/
public static void main(String[] args) throws NumberFormatException, IOException{
FileReader file = new FileReader(new File("Edges.txt"));
BufferedReader reader = new BufferedReader(file);
Vertice[] vertices = new Vertice[114];
Edge[] edges = new Edge[290];
readFile(vertices, edges, reader);
/*
for(int z = 0; z < vertices.length; z++){
System.out.println(vertices[z].getName());
}
*/
Vertice town = getGrandForks(vertices);
System.out.println("this is before DFS: " + town.getName());
Weight weight = new Weight();
DFS(vertices, town, edges, weight);
System.out.println(weight.getWeight());
/*
for(int x = 0; x < vertices.length; x++){
System.out.println(vertices[x].getName());
for(int y = 0; y < vertices[x].getConnectedVerticeNum(); y++){
System.out.println(" " + vertices[x].getVertices()[y].getName());
}
}
*/
Edge[] backEdges = new Edge[290];
findBackEdge(edges, backEdges);
for(int x = 0; x < backEdges.length; x++){
if(backEdges[x] == null){
break;
}
//System.out.println(backEdges[x].getName1().getName() + " " + backEdges[x].getName2().getName() + " " + backEdges[x].getWeight());
}
Vertice name = null;
name = findVertice(vertices, "Grand Forks");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Seattle");
System.out.println();
name = null;
name = findVertice(vertices, "Seattle");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "San Diego");
System.out.println();
name = null;
name = findVertice(vertices, "San Diego");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Houston");
System.out.println();
name = null;
reset(vertices);
name = findVertice(vertices, "Houston");
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Key West");
System.out.println();
name = null;
name = findVertice(vertices, "Key West");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "New York City");
System.out.println();
name = null;
name = findVertice(vertices, "New York City");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Chicago");
System.out.println();
name = null;
name = findVertice(vertices, "Chicago");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Grand Forks");
}
}
Here is the data file we are using
Washington, D.C.//Norfolk//208
Washington, D.C.//Baltimore//39
Washington, D.C.//Philadelphia//235
Washington, D.C.//Pittsburgh//251
Washington, D.C.//Charleston, W.VA//380
Washington, D.C.//Charlotte//388
Washington, D.C.//Knoxville//512
Washington, D.C.//Cincinnati//523
Washington, D.C.//Richmond//108
Norfolk//Richmond//99
Knoxville//Nashville//177
Knoxville//Charlotte//231
Knoxville//Cincinnati//254
Knoxville//Raleigh//362
Knoxville//Charleston, SC//403
Charleston, SC//Myrtle Beach//98
Charleston, SC//Savannah//108
Charleston, SC//Charlotte//218
Charleston, W.VA//Pittsburgh//221
Charleston, W.VA//Louisville//257
Charleston, W.VA//Cleveland//260
Charleston, W.VA//Charlotte//314
Charleston, W.VA//Richmond//331
Orlando//Daytona Beach//58
Orlando//Tampa//84
Orlando//Lake City//160
Orlando//Miami//236
Tallahassee//Lake City//111
Tallahassee//Montgomery//208
Tallahassee//Tampa//252
Tallahassee//Mobile//253
Tallahassee//Atlanta//275
Atlanta//Birmingham//149
Atlanta//Montgomery//161
Atlanta//Knoxville//230
Atlanta//Charlotte//249
Atlanta//Nashville//252
Atlanta//Savannah//256
Atlanta//Lake City//292
Atlanta//Charleston, SC//329
Atlanta//Jacksonville//354
Atlanta//Memphis//394
Memphis//Little Rock//138
Memphis//Nashville//208
Memphis//Jackson//212
Memphis//Birmingham//241
Memphis//Springfield//281
Memphis//St. Louis//283
Jacksonville//Raleigh//536
Jacksonville//Charlotte//399
Jacksonville//Tampa//190
Jacksonville//Savannah//138
Jacksonville//Daytona Beach//99
Jacksonville//Lake City//65
Lake City//Tampa//169
Miami//Tampa//266
Miami//Key West//156
Miami//Daytona Beach//270
Kansas City//Topeka//65
Kansas City//Springfield//170
Kansas City//Wichita//183
Kansas City//Des Moines//197
Wilmington//Norfolk//259
Wilmington//Richmond//255
Wilmington//Myrtle Beach//71
Grand Forks//Fargo//76
Grand Forks//Minot//210
Grand Forks//Duluth//268
Duluth//Madison//340
Des Moines//Madison//373
Milwaukee//Madison//78
Chicago//Milwaukee//91
Chicago//Madison//152
Chicago//Indianapolis//177
Chicago//Grand Rapids//190
Chicago//St. Louis//302
Chicago//Cleveland//345
Chicago//Des Moines//362
Chicago//Nashville//473
Chicago//Kansas City//557
Chicago//Detroit//300
Detroit//Grand Rapids//157
Detroit//Cleveland//173
Detroit//Columbus//206
Detroit//Cincinnati//260
Detroit//Indianapolis//283
Detroit//Buffalo, NY//417
Buffalo, NY//Cleveland//194
Buffalo, NY//Binghamton//220
Buffalo, NY//Albany//289
Binghamton//Albany//137
Cincinnati//Louisville//102
Cincinnati//Indianapolis//108
Cincinnati//Columbus//109
Cincinnati//Columbus//202
Cincinnati//St. Louis//353
Montgomery//Birmingham//92
Montgomery//Mobile//171
Montgomery//Jackson//251
New York City//Hartford//118
New York City//Albany//160
New York City//Harrisburg//174
New York City//Binghamton//199
New York City//Cleveland//481
New York City//Philadelphia//99
Harrisburg//Philadelphia//105
Baltimore//Philadelphia//98
Boston//Hartford//101
Boston//Portland, ME//103
Boston//Albany//177
Denver//Cheyenne//102
Denver//Lamar//206
Denver//Oakley//247
Denver//North Platte//290
Denver//Cortez//411
Denver//Albuquerque//457
Denver//Salt Lake City//529
Denver//St. George//648
Portland, ME//Bangor//132
Portland, OR//Eugene//115
Portland, OR//Seattle//180
Portland, OR//Riley//268
Portland, OR//Crescent City//346
Portland, OR//Spokane//400
Portland, OR//Boise//439
Reno//Winnemucca//164
Reno//Yosemite Village//213
Reno//Ely//331
Reno//Riley//342
Boise//Riley//210
Boise//Twin Falls//123
Boise//Winnemucca//257
Boise//Spokane//379
Boise//Seattle//499
Spokane//Seattle//276
Bismarck//Minot//106
Bismarck//Fargo//194
Bismarck//Pierre//209
Bismarck//Rapid City//358
Bismarck//Billings//418
Bismarck//Malta//430
Rapid City//Pierre//174
Rapid City//Buffalo, WY//216
Rapid City//Cheyenne//290
Rapid City//Sioux Falls//350
Phoenix//Tucson//112
Phoenix//Flagstaff//141
Phoenix//Springerville//236
Phoenix//San Diego//368
Phoenix//El Paso//404
Los Angeles//Phoenix//393
Los Angeles//San Diego//118
Los Angeles//Barstow//138
Los Angeles//Yosemite Village//313
Los Angeles//Reno//522
San Francisco//Los Angeles//384
San Francisco//Reno//228
San Francisco//Barstow//442
San Francisco//Yosemite Village//193
San Francisco//Crescent City//371
San Francisco//Eugene//540
Riley//Eugene//230
Las Vegas//St. George//122
Las Vegas//Barstow//155
Las Vegas//Ely//282
Las Vegas//Phoenix//288
Las Vegas//Reno//442
Las Vegas//Salt Lake City//423
Salt Lake City//Twin Falls//222
Salt Lake City//Rawlins//294
Salt Lake City//Ely//294
Salt Lake City//St. George//305
Salt Lake City//Cortez//348
Salt Lake City//Winnemucca//362
Salt Lake City//Helena//482
Salt Lake City//Old Faithful//482
Raleigh//Wilmington//127
Raleigh//Richmond//156
Raleigh//Norfolk//170
Cleveland//Pittsburgh//141
Cleveland//Columbus//146
Cleveland//Des Moines//677
San Antonio//Eagle Pass//142
San Antonio//Laredo//154
San Antonio//Houston//201
San Antonio//Brownsville//281
San Antonio//Big Spring//298
San Antonio//El Paso//552
San Antonio//Dallas//273
Dallas//Oklahoma City//208
Dallas//Houston//237
Dallas//Big Spring//266
Dallas//Springfield//282
Dallas//Little Rock//315
Dallas//Amarillo//367
Dallas//Jackson//417
Dallas//New Orleans//509
Omaha//Des Moines//143
Omaha//Topeka//163
Omaha//Sioux Falls//175
Omaha//Kansas City//194
Omaha//North Platte//298
Omaha//Liberal//489
Omaha//Rapid City//539
Minneapolis//Duluth//152
Minneapolis//Fargo//242
Minneapolis//Sioux Falls//247
Minneapolis//Madison//260
Minneapolis//Des Moines//286
Minneapolis//Pierre//399
Minneapolis//Omaha//409
Minneapolis//St. Louis//540
New Orleans//Mobile//153
New Orleans//Jackson//183
New Orleans//Birmingham//354
New Orleans//Houston//363
Buffalo, WY//Old Faithful//296
Buffalo, WY//Billings//168
Buffalo, WY//Rawlins//236
Old Faithful//Rawlins//320
Rawlins//Cheyenne//146
North Platte//Cheyenne//215
North Platte//Oakley//158
North Platte//Pierre//264
Charlotte//Raleigh//175
Charlotte//Myrtle Beach//180
Charlotte//Wilmington//188
Nashville//Louisville//180
Nashville//St. Louis//312
Nashville//Birmingham//192
Jackson//Birmingham//234
Pittsburgh//Harrisburg//218
Pittsburgh//Columbus//184
Indianapolis//St. Louis//244
Indianapolis//Columbus//179
Indianapolis//Louisville//124
Brownsville//Houston//365
Brownsville//Laredo//204
Eagle Pass//Laredo//124
Billings//Malta//206
Billings//Helena//243
Helena//Old Faithful//216
Helena//Malta//293
Helena//Missoula//116
Spokane//Missoula//198
Twin Falls//Missoula//401
Twin Falls//Ely//255
Little Rock//Springfield//219
Little Rock//Jackson//267
Little Rock//Houston//315
Little Rock//Oklahoma City//336
Little Rock//St. Louis//350
St. Louis//Des Moines//387
St. Louis//Louisville//259
St. Louis//Kansas City//250
St. Louis//Springfield//224
Malta//Minot//457
Fargo//Minot//268
Fargo//Duluth//259
Fargo//Sioux Falls//253
Flagstaff//St. George//286
Flagstaff//Cortez//263
Flagstaff//Barstow//348
San Diego//Barstow//181
El Paso//Big Spring//344
El Paso//Amarillo//412
El Paso//Eagle Pass//484
El Paso//Houston//746
El Paso//Tucson//324
El Paso//Albuquerque//270
Albuquerque//Lamar//393
Albuquerque//Flagstaff//325
Albuquerque//Amarillo//296
Albuquerque//Cortez//273
Albuquerque//Springerville//233
Albuquerque//Big Spring//418
Albuquerque//Liberal//421
Amarillo//Liberal//164
Amarillo//Oklahoma City//259
Amarillo//Big Spring//224
Amarillo//Lamar//228
Liberal//Lamar//168
Liberal//Oakley//143
Liberal//Wichita//209
Topeka//Wichita//138
Topeka//Oakley//289
Topeka//Liberal//361
Oklahoma City//Wichita//156
Oklahoma City//Liberal//256
Oklahoma City//Springfield//283
here is our current output
this is the route to from destination to start: Seattle --- To --- Boise
this is the route to from destination to start: Boise --- To --- Twin Falls
this is the route to from destination to start: Twin Falls --- To --- Salt Lake City
this is the route to from destination to start: Salt Lake City --- To --- Rawlins
this is the route to from destination to start: Rawlins --- To --- Cheyenne
this is the route to from destination to start: Cheyenne --- To --- Rapid City
this is the route to from destination to start: Rapid City --- To --- Bismarck
this is the route to from destination to start: Bismarck --- To --- Fargo
this is the route to from destination to start: Fargo --- To --- Grand Forks
this is the route to from destination to start: San Diego --- To --- Los Angeles
this is the route to from destination to start: Los Angeles --- To --- San Francisco
this is the route to from destination to start: San Francisco --- To --- Eugene
this is the route to from destination to start: Eugene --- To --- Portland, OR
this is the route to from destination to start: Portland, OR --- To --- Seattle
this is the route to from destination to start: Houston --- To --- El Paso
this is the route to from destination to start: El Paso --- To --- Phoenix
this is the route to from destination to start: Phoenix --- To --- San Diego
this is the route to from destination to start: Key West --- To --- Miami
this is the route to from destination to start: Miami --- To --- Orlando
this is the route to from destination to start: Orlando --- To --- Lake City
this is the route to from destination to start: Lake City --- To --- Atlanta
this is the route to from destination to start: Atlanta --- To --- Birmingham
this is the route to from destination to start: Birmingham --- To --- Memphis
this is the route to from destination to start: Memphis --- To --- Little Rock
this is the route to from destination to start: Little Rock --- To --- Houston
this is the route to from destination to start: New York City --- To --- Harrisburg
this is the route to from destination to start: Harrisburg --- To --- Pittsburgh
this is the route to from destination to start: Pittsburgh --- To --- Columbus
this is the route to from destination to start: Columbus --- To --- Cincinnati
this is the route to from destination to start: Cincinnati --- To --- Knoxville
this is the route to from destination to start: Knoxville --- To --- Atlanta
this is the route to from destination to start: Atlanta --- To --- Lake City
this is the route to from destination to start: Lake City --- To --- Orlando
this is the route to from destination to start: Orlando --- To --- Miami
this is the route to from destination to start: Miami --- To --- Key West
this is the route to from destination to start: Chicago --- To --- Cleveland
this is the route to from destination to start: Cleveland --- To --- New York City
this is the route to from destination to start: Grand Forks --- To --- Duluth
this is the route to from destination to start: Duluth --- To --- Madison
this is the route to from destination to start: Madison --- To --- Chicago
The ones that do not work at this point are shortest path from
key west to houston
New York City to key west
Seattle to Grand Forks
Explanation / Answer
import java.io;
import java.util;
import java.lang;
public class Main {
public static void Dikstras(Vertice[] vertices, Vertice src){
Vertice name = null;
int weight = 0;
boolean check = false;
int edgeWeight = 0;
Edge edge = null;
src.setVisited(true);
for(int x = 0; x < src.getConnectedEdgesNum(); x++){
if(src.getEdge(x).getName1().getName().equals(src.getName())){
name = src.getEdge(x).getName2();
}
if(src.getEdge(x).getName2().getName().equals(src.getName())){
name = src.getEdge(x).getName1();
}
for(int y = 0; y < vertices.length; y++){
edgeWeight = src.getEdge(x).getWeight();
weight = src.getEdge(x).getWeight() + src.getValue();
check = name.getName().equals(vertices[y].getName());
if (check){
if(vertices[y].getName().equals("Seattle")){
int r = 0;
r = 20;
}
if(vertices[y].getValue() > weight){
vertices[y].setValue(weight);
vertices[y].setParent(src);
}
break;
}
}
}
for(int y = 0; y < src.getConnectedVerticeNum(); y++){
for(int z = 0; z < vertices.length; z++){
if (src.getVertices()[y].getName().equals(vertices[z].getName())){
name = vertices[z];
break;
}
}
if(name.getVisited() == false){
Dikstras(vertices, name);
}
}
}
public static void reset(Vertice[] vertices){
for(int x = 0; x < vertices.length; x++){
vertices[x].setVisited(false);
vertices[x].setParent(null);
vertices[x].setValue(Integer.MAX_VALUE);
}
}
public static void DFS(Vertice[] towns, Vertice town, Edge[] roads, Weight weight){
System.out.println("This is the towns traversed through DFS: "+ town.getName());
town.setVisited(true);
town.setValue(weight.getWeight());
for(int x = 0; x < town.getConnectedVerticeNum(); x++){
String name = town.getEdge(x).getName(town).getName();
Vertice newTown = findTown(name, towns);
int newTownWeight = town.getEdge(x).getWeight();
/* not needed at this point
if(newTown.getVisited() == true){
setBackEdge(town.getEdge(x));
}
*/
if(newTown.getVisited() == false){
setDiscoveryEdge(town.getEdge(x), roads);
weight.addWeight(newTownWeight);
DFS(towns, newTown, roads, weight);
}
}
}
public static Vertice findTown(String name, Vertice[] towns){
Vertice town = null;
for(int x = 0; x < towns.length; x++){
if(towns[x].getName().equals(name)){
town = towns[x];
}
}
return town;
}
public static void findBackEdge(Edge[] roads, Edge[] backEdge){
int counter = 0;
for(int x = 0; x < roads.length; x++){
if(roads[x].getDiscoverEdge() == false){
backEdge[counter] = roads[x];
counter++;
}
}
}
public static void setDiscoveryEdge(Edge road, Edge[] roads){
int whileCheck = 0;
for(whileCheck = 0; whileCheck < roads.length; whileCheck++){
if(roads[whileCheck].equals(road)){
roads[whileCheck].setDiscoveryEdge();
return;
}
}
}
public static Vertice getGrandForks(Vertice[] towns){
Vertice town = null;
for(int x = 0; x < towns.length; x++){
if(towns[x].getName().equals("Grand Forks")){
town = towns[x];
return town;
}
}
return town;
}
public static void readFile(Vertice[] towns, Edge[] roads, BufferedReader reader) throws NumberFormatException, IOException{
String line = null;
String[] tokens = new String[3];
int edgeValue = 0;
Vertice first = null;
Vertice second = null;
Edge edge = null;
while((line = reader.readLine()) != null){
tokens = line.split("//");
//System.out.println(tokens[0] + " " + tokens[1]+ " " + tokens[2]);
edgeValue = Integer.parseInt(tokens[2]);
first = new Vertice(tokens[0]);
second = new Vertice(tokens[1]);
edge = new Edge(first, second, edgeValue);
//Add road to the list
boolean check = false;
for(int x = 0; x < roads.length; x++){
if(roads[x] == null){
roads[x] = edge;
}
if(roads[x].getName1().equals(edge.getName1()) || roads[x].getName1().equals(edge.getName2())){
if(roads[x].getName2().equals(edge.getName2()) || roads[x].getName1().equals(edge.getName2())){
check = true;
break;
}
}
}
//iterate through until you hit a null to add at that location
if(check == false){
for(int x = 0; x < roads.length; x++){
if(roads[x] == null){
roads[x] = edge;
}
}
}
//Add towns to list
check = false;
boolean check1 = false;
int numStore = 0;
int numStore1 = 0;
for(int x = 0; x < towns.length; x++){
if(towns[x] == null){
break;
}
if(towns[x].getName().equals(tokens[0])){
check = true;
numStore = x;
first = towns[x];
}
if(towns[x].getName().equals(tokens[1])){
check1 = true;
numStore1 = x;
second = towns[x];
}
if(check == true && check1 == true){
break;
}
}
if(check == false){
for(int x = 0; x < towns.length; x++){
if(towns[x] == null){
towns[x] = first;
numStore = x;
towns[x].addEdge(edge);
break;
}
}
}else{
towns[numStore].addVerticie(second);
towns[numStore].addEdge(edge);
}
if(check1 == false){
for(int x = 0; x < towns.length; x++){
if(towns[x] == null){
towns[x] = second;
numStore1 = x;
towns[x].addEdge(edge);
break;
}
}
}else{
towns[numStore1].addVerticie(first);
towns[numStore1].addEdge(edge);
}
if(check == false){
towns[numStore].addVerticie(second);
}
if(check1 == false){
towns[numStore1].addVerticie(first);
}
}
}
public static void printParents(Vertice[] vertices, String stringName){
Vertice name = null;
Vertice parent = null;
String parentName = "";
for(int x = 0; x < vertices.length; x++){
if(vertices[x].getName().equals(stringName)){
name = null;
name = vertices[x];
while(name != null){
if(name.getParent() == null){
break;
}
System.out.println("this is the route to from destination to start: " + name.getName() + " --- To --- " + name.getParent().getName());
parent = name.getParent();
parentName = parent.getName();
for(int y = 0; y < vertices.length; y++){
if(parentName.equals(vertices[y].getName())){
name = vertices[y];
}
}
}
}
}
}
public static Vertice findVertice(Vertice[] vertices, String name){
Vertice node = null;
for(int x =0; x < vertices.length; x++){
if(vertices[x].getName().equals(name)){
node = vertices[x];
}
}
return node;
}
public static void main(String[] args) throws NumberFormatException, IOException{
FileReader file = new FileReader(new File("Edges.txt"));
BufferedReader reader = new BufferedReader(file);
Vertice[] vertices = new Vertice[114];
Edge[] edges = new Edge[290];
readFile(vertices, edges, reader);
/*
for(int z = 0; z < vertices.length; z++){
System.out.println(vertices[z].getName());
}
*/
Vertice town = getGrandForks(vertices);
System.out.println("this is before DFS: " + town.getName());
Weight weight = new Weight();
DFS(vertices, town, edges, weight);
System.out.println(weight.getWeight());
/*
for(int x = 0; x < vertices.length; x++){
System.out.println(vertices[x].getName());
for(int y = 0; y < vertices[x].getConnectedVerticeNum(); y++){
System.out.println(" " + vertices[x].getVertices()[y].getName());
}
}
Edge[] backEdges = new Edge[290];
findBackEdge(edges, backEdges);
for(int x = 0; x < backEdges.length; x++){
if(backEdges[x] == null){
break;
}
//System.out.println(backEdges[x].getName1().getName() + " " + backEdges[x].getName2().getName() + " " + backEdges[x].getWeight());
}
Vertice name = null;
name = findVertice(vertices, "Grand Forks");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Seattle");
System.out.println();
name = null;
name = findVertice(vertices, "Seattle");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "San Diego");
System.out.println();
name = null;
name = findVertice(vertices, "San Diego");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Houston");
System.out.println();
name = null;
reset(vertices);
name = findVertice(vertices, "Houston");
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Key West");
System.out.println();
name = null;
name = findVertice(vertices, "Key West");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "New York City");
System.out.println();
name = null;
name = findVertice(vertices, "New York City");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Chicago");
System.out.println();
name = null;
name = findVertice(vertices, "Chicago");
reset(vertices);
name.setValue(0);
Dikstras(vertices, name);
printParents(vertices, "Grand Forks");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.