SSSP (SINGLE SOURCE SHORTEST PATH) Write the programs that performs the given ta
ID: 3836480 • Letter: S
Question
SSSP (SINGLE SOURCE SHORTEST PATH)
Write the programs that performs the given tasks of the graph below using JAVA. PLEASE WRITE THE CODE TO READ IN THE DATA FROM A TEXT FILE. The graph model is an undirected graph of the US towns and roads whose weight is a distance between two towns, given in the data.
QUESTION
Find the shortest path from Grand Forks, through the following routes connecting the chosen 6 towns: Grand Forks route 1 Seattle (WA@NW) route 2 San Diego (CA@SW) route 3 Houston (TX@SC) route 4 Key West (FL@SE) route 5 New York City (NY@NE) route 6 Chicago (IL@NC) route 7 Grand Forks.
The final route of the Shortest Path:
a) a list of the towns on the shortest path b/t a pair of towns in each route
b) the subtotal distance of the shortest path b/t a pair of towns in each route
c) the final total distance of the entire route of the shortest path.
DATA
u v weight 114 vertices 290 edges 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 283Explanation / Answer
import java.util.InputMismatchException;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
public class SSSP
{
private boolean settle_vertex[];
private boolean unsettle_vertex[];
private int _distance[];
private int weightAdjacencyMatrix[][];
private int _totalVertices;
public SSSP(int _totalVertices)
{
this._totalVertices = _totalVertices;
this.settle_vertex = new boolean[_totalVertices + 1];
this.unsettle_vertex = new boolean[_totalVertices + 1];
this._distance = new int[_totalVertices + 1];
this.weightAdjacencyMatrix = new int[_totalVertices + 1][_totalVertices + 1];
}
public void getShortestPath(int sourceVertex, int weightAdjacencyMatrix[][])
{
int evalNode;
for (int _vertex = 1; _vertex <= _totalVertices; _vertex++)
{
_distance[_vertex] = Integer.MAX_VALUE;
}
for (int sourcevertex = 1; sourcevertex <= _totalVertices; sourcevertex++)
{
for (int destinationvertex = 1; destinationvertex <= _totalVertices; destinationvertex++)
{
this.weightAdjacencyMatrix[sourcevertex][destinationvertex]
= weightAdjacencyMatrix[sourcevertex][destinationvertex];
}
}
unsettle_vertex[sourceVertex] = true;
_distance[sourceVertex] = 0;
while (getUnsettleTotal(unsettle_vertex) != 0)
{
evalNode = getMinimumNode(unsettle_vertex);
unsettle_vertex[evalNode] = false;
settle_vertex[evalNode] = true;
solveNeighbours(evalNode);
}
}
public int getUnsettleTotal(boolean unsettle_vertex[])
{
int _tempCount = 0;
for (int _vertex = 1; _vertex <= _totalVertices; _vertex++)
{
if (unsettle_vertex[_vertex] == true)
{
_tempCount++;
}
}
return _tempCount;
}
public int getMinimumNode(boolean unsettle_vertex[])
{
int MIN = Integer.MAX_VALUE;
int _node = 0;
for (int _vertex = 1; _vertex <= _totalVertices; _vertex++)
{
if (unsettle_vertex[_vertex] == true && _distance[_vertex] < MIN)
{
_node = _vertex;
MIN = _distance[_vertex];
}
}
return _node;
}
public void solveNeighbours(int evalNode)
{
int edge_dist = -1;
int temp_dist = -1;
for (int dest_node = 1; dest_node <= _totalVertices; dest_node++)
{
if (settle_vertex[dest_node] == false)
{
if (weightAdjacencyMatrix[evalNode][dest_node] != Integer.MAX_VALUE)
{
edge_dist = weightAdjacencyMatrix[evalNode][dest_node];
temp_dist = _distance[evalNode] + edge_dist;
if (temp_dist < _distance[dest_node])
{
_distance[dest_node] = temp_dist;
}
unsettle_vertex[dest_node] = true;
}
}
}
}
public static void main(String args[])
{
int adjacency_matrix[][];
int total_vertices;
int sourceVertex = 0;
int temp = 0;
Scanner sc1 = new Scanner(System.in);
try
{
System.out.println("Enter total vertices");
total_vertices = sc1.nextInt();
adjacency_matrix = new int[total_vertices + 1][total_vertices + 1];
File file = new File("weights.txt");
try {
Scanner sc = new Scanner(file);
while (sc.hasNextLine()) {
String line = sc.nextLine();
String[] data = line.split(" ");
for(int j=0;j<total_vertices;j++){//filling matrix
adjacency_matrix[temp][j] = Integer.parseInt(data[j]);
}
temp++;
}
sc.close();
}
catch (FileNotFoundException e) {
e.printStackTrace();
}
System.out.println("Enter source sity ");
sourceVertex = sc1.nextInt();
SSSP obj = new SSSP(total_vertices);
obj.getShortestPath(sourceVertex, adjacency_matrix);
System.out.println("The Shorted Path to all cities is: ");
for (int i = 1; i <= obj._distance.length - 1; i++)
{
System.out.println(sourceVertex + " to " + i + " is "+ obj._distance[i]);
}
}
catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input");
}
sc1.close();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.