Traveling Salesperson Problem with a Stack - Shortest Path Tree. This is a non-r

Question

Traveling Salesperson Problem with a Stack - Shortest Path Tree. This is a non-recursive algorithm. You need to set up the adjacency matrix. The language is JAVA

create an empty stack, call it pathStack

create an empty array of N elements, call it visitedCities // N== # of cities

//assume start city is city 0

set city 0 as visited in visitedCities array

push city 0 to pathStack

set closestCity to 0

set minFlag to false

Output start city
while pathStack is not empty do

set currentCity with top value of pathStack

set min to Integer.MAX_VALUE //minimum distance

for all the remaining cities starting city 1 to N do

if (distance from currentCity to city i is not 0 AND

city i is not visited)

if (distance from currentCity to city i is less

than min)

min = distance from currentCity to city iclosestCity = iset minFlag to true

endif

endif

endfor

if(minflag)

set closestCity in visitedCities as visited

push closestCity to pathStack

Output closestCity

set minFlag to false

continue

endif

pop the top element from pathStack

endwhile

Explanation / Answer

****************************PROGRAM*********************************************

package tsp;
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;

public class TravSP
{
private int nNode;
private Stack<Integer> stk;

public TravSP()
{
stk = new Stack<Integer>();
}

public void tsp(int adj_Matrix[][])
{
nNode = adj_Matrix[1].length - 1;
int[] visitedArr = new int[nNode + 1];
visitedArr[1] = 1;
stk.push(1);
int element, dest = 0, i;
int minNum = Integer.MAX_VALUE;
boolean minFlag = false;
System.out.print(1 + " ");
while (!stk.isEmpty())
{
element = stk.peek();
i = 1;
minNum = Integer.MAX_VALUE;
while (i <= nNode)
{
if (adj_Matrix[element][i] > 1 && visitedArr[i] == 0)
{
if (minNum > adj_Matrix[element][i])
{
minNum = adj_Matrix[element][i];
dest = i;
minFlag = true;
}
}
i++;
}
if (minFlag)
{
visitedArr[dest] = 1;
stk.push(dest);
System.out.print(dest + " ");
minFlag = false;
continue;
}
stk.pop();
}
}

public static void main(String... arg)
{
int totalNodes;
Scanner scanner = null;
try
{
  
scanner = new Scanner(System.in);
System.out.println("Please enter the total number of nodes in your graph");
totalNodes = scanner.nextInt();
int adjacency_matrix[][] = new int[totalNodes + 1][totalNodes + 1];
System.out.println("Enter the adjacency matrix for the graph:");
for (int i = 1; i <= totalNodes; i++)
{
for (int j = 1; j <= totalNodes; j++)
{
adjacency_matrix[i][j] = scanner.nextInt();
}
}
for (int i = 1; i <= totalNodes; i++)
{
for (int j = 1; j <= totalNodes; j++)
{
if (adjacency_matrix[i][j] == 1
&& adjacency_matrix[j][i] == 0)
{
adjacency_matrix[j][i] = 1;
}
}
}
System.out.println("The cities are visited are as follows: ");
TravSP tspNearestNeighbour = new TravSP();
tspNearestNeighbour.tsp(adjacency_matrix);
}
catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}

********************************output*************************************************

Please enter the total number of nodes in the graph
5
Enter the adjacency matrix for the graph:
1
5
4
6
7
8
9
4
5
6
1
2
8
5
6
4
6
4
2
5
3
6
8
7
1
The cities are visited are as follows:
1   3   2   4   5  

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.