Dynamic Programming Algorithm for the Traveling Salesperson

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<>();
  }

  private void TS_meth1(int adjacencyMatrix[][])
  {
    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)
        {
          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 + "\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];
      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 cities are visited in the following order: ");
      TravelingSalesmanNearestNeighbour TravelingSalesmanNearestNeighbour = new TravelingSalesmanNearestNeighbour();
      TravelingSalesmanNearestNeighbour.TS_meth1(adjacency_matrix);
    } catch (InputMismatchException inputMismatch)
    {
      System.out.println("Wrong Input format");
    }
    assert scanner != null;
    scanner.close();
  }
}