Travelling Salesman Problem with Row and Column Minimization, and Penalty Rule using Java

import java.io.*;
import java.util.*;

public class Main {
  static int cost = 0;
  static String path = "";

  // NOTE: *Use only one test case per running of program because they have the same identifier*
  // TEST CASE 1: (Output should 30 from M3S2) (UNCOMMENT below to enable)
  static char[] letters = {'A', 'B', 'C', 'D', 'E'};
  static int val[][] = {{Integer.MAX_VALUE, 7, 6, 8, 4},
                        {7, Integer.MAX_VALUE, 8, 5, 6},
                        {6, 8, Integer.MAX_VALUE, 9, 7},
                        {8, 5, 9, Integer.MAX_VALUE, 8},
                        {4, 6, 7, 8, Integer.MAX_VALUE}};

  //     TEST CASE 2: (Output should 17 from TSP EXER1) (UNCOMMENT below to enable)
//  static char[] letters = {'A', 'B', 'C', 'D', 'E'};
//  static int val[][] = {{Integer.MAX_VALUE, 3, 6, 2, 3},
//                        {3, Integer.MAX_VALUE, 5, 2, 3},
//                        {6, 5, Integer.MAX_VALUE, 6, 5},
//                        {2, 2, 6, Integer.MAX_VALUE, 6},
//                        {3, 3, 5, 6, Integer.MAX_VALUE}};

//      TEST CASE 3: (Output should be 110 TSP EXER2) (UNCOMMENT below to enable)
//  static char[] letters = {'A', 'B', 'C', 'D', 'E', 'F'};
//  static int val[][]= {{Integer.MAX_VALUE, 20, 23, 27, 29, 34},
//                       {21, Integer.MAX_VALUE, 19, 26, 31, 24},
//                       {26, 28, Integer.MAX_VALUE, 15, 36, 26},
//                       {25, 26, 25, Integer.MAX_VALUE, 23, 28},
//                       {23, 40, 13, 31, Integer.MAX_VALUE, 10},
//                       {27, 18, 12, 35, 16, Integer.MAX_VALUE}};

  private boolean Check(int[][] table) {
    for (int i = 0; i < (int) table.length; i++) {
      for (int j = 0; j < (int) table[i].length; j++) {
        if (table[i][j] != 0 && table[i][j] != Integer.MAX_VALUE) {
          return false;
        }
      }
    }
    return true;
  }

  private boolean Zeroes(Vector<Integer> temp) {
    for (int i = 0; i < (int) temp.size(); i++) {
      if (temp.elementAt(i) == 0) {
        return true;
      }
    }
    return false;
  }

  private int[][] RowMinimization(int[][] table) {
    for (int i = 0; i < (int) table.length; i++) {
      Vector<Integer> temp = new Vector<Integer>();
      for (int j = 0; j < (int) table.length; j++) {
        temp.add(table[i][j]);
      }
      if (Zeroes(temp)) {
        continue;
      }
      int minimum = Integer.MAX_VALUE;
      for (int j = 0; j < (int) table[i].length; j++) {
        minimum = Math.min(minimum, table[i][j]);
      }
      for (int j = 0; j < (int) table[i].length; j++) {
        if (table[i][j] != Integer.MAX_VALUE) {
          table[i][j] = table[i][j] - minimum;
        }
      }
    }
    return table;
  }

  private int[][] ColumnMinimization(int[][] table) {
    for (int i = 0; i < (int) table.length; i++) {
      Vector<Integer> temp = new Vector<Integer>();
      for (int j = 0; j < (int) table.length; j++) {
        temp.add(table[j][i]);
      }
      if (Zeroes(temp)) {
        continue;
      }
      int minimum = Integer.MAX_VALUE;
      for (int j = 0; j < (int) table[i].length; j++) {
        minimum = Math.min(minimum, table[j][i]);
      }
      for (int j = 0; j < (int) table[i].length; j++) {
        if (table[j][i] != Integer.MAX_VALUE) {
          table[j][i] = table[j][i] - minimum;
        }
      }
    }
    return table;
  }

  private int[][] Penalty(int[][] table) {
    int[][] temp = new int[(int) table.length][(int) table.length];
    for (int i = 0; i < (int) table.length; i++) {
      for (int j = 0; j < (int) table[i].length; j++) {
        temp[i][j] = table[i][j];
      }
    }
    int key = Integer.MIN_VALUE;
    for (int i = 0; i < (int) temp.length; i++) {
      for (int j = 0; j < (int) temp[i].length; j++) {
        if (table[i][j] == 0) {
          int row_minimum = Integer.MAX_VALUE;
          for (int k = 0; k < (int) temp[i].length; k++) {
            if (k != j) {
              row_minimum = Math.min(row_minimum, table[i][k]);
            }
          }
          int column_minimum = Integer.MAX_VALUE;
          for (int k = 0; k < (int) temp[i].length; k++) {
            if (k != i) {
              column_minimum = Math.min(column_minimum, table[k][j]);
            }
          }
          temp[i][j] = row_minimum + column_minimum;
          key = Math.max(key, temp[i][j]);
        }
      }
    }
    int row_index = -1;
    int column_index = -1;
    for (int i = 0; i < (int) temp.length; i++) {
      for (int j = 0; j < (int) temp[i].length; j++) {
        if (table[i][j] == 0 && temp[i][j] == key) {
          row_index = i;
          column_index = j;
          cost += val[i][j];
          path += String.valueOf(letters[i]);
          path += String.valueOf(letters[j]);
          break;
        }
      }
      if (row_index != -1 && column_index != -1) {
        break;
      }
    }
    table[column_index][row_index] = Integer.MAX_VALUE;
    for (int i = 0; i < (int) table.length; i++) {
      for (int j = 0; j < (int) table[i].length; j++) {
        if (i == row_index || j == column_index) {
          table[i][j] = Integer.MAX_VALUE;
        }
      }
    }
    return table;
  }

  public static void main(String[] args) {
      Main object = new Main();
      int table[][] = new int[(int) val.length][(int) val.length];
      for (int i = 0; i < (int) table.length; i++) {
        for (int j = 0; j < (int) table[i].length; j++) {
          table[i][j] = val[i][j];
        }
      }
      while (true) {
        if (object.Check(table)) {
            break;
        }
        table = object.RowMinimization(table);
        table = object.ColumnMinimization(table);
        table = object.Penalty(table);
      }
      System.out.println("Table Status:");
      System.out.print(" ");
      for (int i = 0; i < (int) letters.length; i++) {
        System.out.print(" " + letters[i]);
      }
      System.out.println("");
      for (int i = 0; i < (int) table.length; i++) {
        System.out.print(letters[i] + " ");
        for (int j = 0; j < (int) table[i].length; j++) {
          System.out.print((table[i][j] == Integer.MAX_VALUE ? "-" : table[i][j]) + " ");
        }
        System.out.println("");
      }
      for (int i = 0; i < (int) table.length; i++) {
        int zeroes = 0;
        for (int j = 0; j < (int) table.length; j++) {
          if (table[i][j] == 0) {
            zeroes++;
          }
        }
        int minimum_per_row = Integer.MAX_VALUE;
        int row_index = -1;
        int column_index = -1;
        for (int j = 0; j < (int) table.length; j++) {
          if (table[i][j] == 0) {
            boolean checker = false;
            if (j == 0) {
              for (int k = 0; k < (int) table[i].length; k++) {
                if (table[k][j] == 0 && k != i) {
                  checker = true;
                  break;
                }
              }
            }
            if (checker && zeroes > 1) {
              continue;
            }
            if (val[i][j] < minimum_per_row) {
              minimum_per_row = val[i][j];
              row_index = i;
              column_index = j;
            }
          }
        }
        if (minimum_per_row != Integer.MAX_VALUE) {
          String connected = String.valueOf(letters[row_index]) + String.valueOf(letters[column_index]);
          path += connected;
          cost += minimum_per_row;
        }
      }
      Vector<String> separate = new Vector<String>();
      for (int i = 0; i < (int) path.length(); i += 2) {
        String temp = String.valueOf(path.charAt(i)) + String.valueOf(path.charAt(i + 1));
        separate.add(temp);
      }
      System.out.println("\nFinal Path:");
      String last_path = "";
      boolean[] visited = new boolean[(int) separate.size()];
      Arrays.fill(visited, false);
      for (int i = 0; i < (int) separate.size(); i++) {
        if (separate.elementAt(i).charAt(0) == 'A') {
          visited[i] = true;
          last_path += String.valueOf(separate.elementAt(i).charAt(0)) + "->" + String.valueOf(separate.elementAt(i).charAt(1));
          break;
        }
      }
      while (true) {
        boolean checker = true;
        for (int i = 0; i < (int) visited.length; i++) {
          if (!visited[i]) {
            checker = false;
            break;
          }
        }
        if (checker) {
          break;
        }
        for (int i = 0; i < (int) separate.size(); i++) {
          if (last_path.charAt((int) last_path.length() - 1) == separate.elementAt(i).charAt(0)) {
            visited[i] = true;
            last_path += ("->" + String.valueOf(separate.elementAt(i).charAt(1)));
            break;
          }
        }
      }
      System.out.println(last_path + " = " + cost + '\n');
   }
}