Hey guys, I need help figuring out how to code a program that would find all pat

Question

Hey guys,

I need help figuring out how to code a program that would find all paths for a specific flight path and print out the shortest path as well, all referring to an ajacency matrix. I have the following theory but I just just do not know how to implement it.

Delta Airlines:

ATL AMS NY SEA SLC

ATL 0 0 1 1 1

AMS 0 0 1 0 1

NY 1 1 0 1 1

SEA 1 0 1 0 1

SLC 1 1 1 1 1

Find routes to SEA to NY:

NY -> SEA

NY -> SLC -> SEA

NY -> ATL -> SEA

NY -> ATL -> SLC -> SEA

Shortests Route:

NY -> SEA

char routes[5][5] = {"ATL", "AMS", "NY", "SEA", "SLC"};

int ATL = { 0 0 1 1 1};

int AMS = {0 0 1 0 1};

int NY = {1 1 0 1 1};

int SEA = {1 0 1 0 1};

int SLC = {1 1 1 1 1};

Thanks in advance.

Explanation / Answer

Program:

import java.util.InputMismatchException;
import java.util.Scanner;

public class DijkstraShortestPath
{
private boolean settled[];
private boolean unsettled[];
private int distances[];
private int adjacencymatrix[][];
private int numberofvertices;

public DijkstraShortestPath(int numberofvertices)
{
this.numberofvertices = numberofvertices;
this.settled = new boolean[numberofvertices + 1];
this.unsettled = new boolean[numberofvertices + 1];
this.distances = new int[numberofvertices + 1];
this.adjacencymatrix = new int[numberofvertices + 1][numberofvertices + 1];
}

public void dijkstraShortestPath(int source, int adjacencymatrix[][])
{
int evaluationnode;
for (int vertex = 1; vertex <= numberofvertices; vertex++)
{
distances[vertex] = Integer.MAX_VALUE;
}

for (int sourcevertex = 1; sourcevertex <= numberofvertices; sourcevertex++)
{
for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
{
this.adjacencymatrix[sourcevertex][destinationvertex]
= adjacencymatrix[sourcevertex][destinationvertex];            
}
}

unsettled[source] = true;
distances[source] = 0;
while (getUnsettledCount(unsettled) != 0)
{
evaluationnode = getNodeWithMinimumDistanceFromUnsettled(unsettled);
unsettled[evaluationnode] = false;
settled[evaluationnode] = true;
evaluateNeighbours(evaluationnode);
}
}

public int getUnsettledCount(boolean unsettled[])
{
int count = 0;
for (int vertex = 1; vertex <= numberofvertices; vertex++)
{
if (unsettled[vertex] == true)
{
count++;
}
}
return count;
}

public int getNodeWithMinimumDistanceFromUnsettled(boolean unsettled[])
{
int min = Integer.MAX_VALUE;
int node = 0;
for (int vertex = 1; vertex <= numberofvertices; vertex++)
{
if (unsettled[vertex] == true && distances[vertex] < min)
{
node = vertex;
min = distances[vertex];
}
}
return node;
}

public void evaluateNeighbours(int evaluationNode)
{
int edgeDistance = -1;
int newDistance = -1;

for (int destinationNode = 1; destinationNode <= numberofvertices; destinationNode++)
{
if (settled[destinationNode] == false)
{
if (adjacencymatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
{
edgeDistance = adjacencymatrix[evaluationNode][destinationNode];
newDistance = distances[evaluationNode] + edgeDistance;
if (newDistance < distances[destinationNode])
{
distances[destinationNode] = newDistance;  
}
unsettled[destinationNode] = true;
}
}
}
}

public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
int source = 0;
Scanner scan = new Scanner(System.in);
try
{
System.out.println("Enter the number of vertices");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];

System.out.println("Enter the Weighted Matrix for the graph");
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
adjacency_matrix[i][j] = scan.nextInt();
if (i == j)
{
adjacency_matrix[i][j] = 0;
continue;
}
if (adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j] = Integer.MAX_VALUE;
}
}
}

System.out.println("Enter the source ");
source = scan.nextInt();

DijkstraShortestPath dijkstrasAlgorithm = new DijkstraShortestPath(number_of_vertices);
dijkstrasAlgorithm.dijkstraShortestPath(source, adjacency_matrix);

System.out.println("The Shorted Path to all nodes are ");
for (int i = 1; i <= dijkstrasAlgorithm.distances.length - 1; i++)
{
System.out.println(source + " to " + i + " is "+ dijkstrasAlgorithm.distances[i]);
   }
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scan.close();
}
}

Result:

Enter the number of vertices
5
Enter the Weighted Matrix for the graph
0 0 1 1 1
0 0 1 0 1
1 1 0 1 1
1 0 1 0 1
1 1 1 1 1
Enter the source
4
The Shorted Path to all nodes are
4 to 1 is 1
4 to 2 is 2
4 to 3 is 1
4 to 4 is 0
4 to 5 is 1

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects