Dynamic Programming Algorithm for the Traveling Salesperson

by Bittle in Dynamic Programming

Problem

Using the java programming language, write a program to implement the Dynamic Programming Algorithm for the Traveling Salesperson.

Solution

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

public class TravelingSalesmanNearestNeighbour
{
private Stack<Integer> stack;

private TravelingSalesmanNearestNeighbour()
{
stack = new Stack<>();
}

{
int 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 + "\t");

while (!stack.isEmpty())
{
element = stack.peek();
i = 1;
min = Integer.MAX_VALUE;
while (i <= num_nodes)
{
if (adjacencyMatrix[element][i] > 1 && visited[i] == 0)
{
{
dst = i;
minFlag = true;
}
}
i++;
}
if (minFlag)
{
visited[dst] = 1;
stack.push(dst);
System.out.print(dst + "\t");
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];
for (int i = 1; i <= node_num1; i++)
{
for (int j = 1; j <= node_num1; j++)
{
}
}
for (int i = 1; i <= node_num1; i++)
{
for (int j = 1; j <= node_num1; j++)
{
{
}
}
}
System.out.println("the cities are visited in the following order: ");
TravelingSalesmanNearestNeighbour TravelingSalesmanNearestNeighbour = new TravelingSalesmanNearestNeighbour();