Using the java programming language: Write a program to implement the Dynamic Pr

Question

Using the java programming language: Write a program to implement the Dynamic Programming Algorithm for the Traveling SalespersonWrite a program to implement the Dynamic Programming Algorithm for the Traveling Salesperson Using the java programming language: Write a program to implement the Dynamic Programming Algorithm for the Traveling SalespersonWrite a program to implement the Dynamic Programming Algorithm for the Traveling Salesperson Using the java programming language: Write a program to implement the Dynamic Programming Algorithm for the Traveling SalespersonWrite a program to implement the Dynamic Programming Algorithm for the Traveling Salesperson

Explanation / Answer

Hi,

Please find below the dynamic implementation code for TSP problem in Java-

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

public class TravallingSalesmanNearestNeighbour
{
private int num_nodes;
private Stack<Integer> stack;

public TravallingSalesmanNearestNeighbour()
{
stack = new Stack<Integer>();
}

public void TS_meth1(int adjacencyMatrix[][])
{
num_nodes = adjacencyMatrix[1].length - 1;
int[] visited = new int[num_nodes + 1];
visited[1] = 1;
stack.push(1);
int element, dst = 0, i;
int min = Integer.MAX_VALUE;
boolean minFlag = false;
System.out.print(1 + " ");

while (!stack.isEmpty())
{
element = stack.peek();
i = 1;
min = Integer.MAX_VALUE;
while (i <= num_nodes)
{
if (adjacencyMatrix[element][i] > 1 && visited[i] == 0)
{
if (min > adjacencyMatrix[element][i])
{
min = adjacencyMatrix[element][i];
dst = i;
minFlag = true;
}
}
i++;
}
if (minFlag)
{
visited[dst] = 1;
stack.push(dst);
System.out.print(dst + " ");
minFlag = false;
continue;
}
stack.pop();
}
}

public static void main(String... arg)
{
int node_num1;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
node_num1 = scanner.nextInt();
int adjacency_matrix[][] = new int[node_num1 + 1][node_num1 + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= node_num1; i++)
{
for (int j = 1; j <= node_num1; j++)
{
adjacency_matrix[i][j] = scanner.nextInt();
}
}
for (int i = 1; i <= node_num1; i++)
{
for (int j = 1; j <= node_num1; j++)
{
if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)
{
adjacency_matrix[j][i] = 1;
}
}
}
System.out.println("the citys are visited as follows");
TravallingSalesmanNearestNeighbour TravallingSalesmanNearestNeighbour = new TravallingSalesmanNearestNeighbour();
TravallingSalesmanNearestNeighbour.TS_meth1(adjacency_matrix);
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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