Реализация метода ветвей и границ на основе задачи коммивояжера

package vetki;
 
import java.io.*;
import java.util.*;
 
 
public class bbstatic {
 
    /*
    Main Function
    Main - Input - Pathname of Input data
    Return - Void - Prints results on screen
    */
 
    public static void main(String[] args) throws FileNotFoundException {
        // Запуск отсчета для времени выполнения
        long start_time = System.currentTimeMillis();
        // Открытие файла данных и определение количества городов
        String filename = "input.txt";
        if (args.length > 0) {
            filename = args[0];
        }
        File f1 = new File(filename);
        System.out.println(f1.getAbsolutePath());
        BufferedReader input = new BufferedReader(new FileReader(f1));
        BufferedReader input1 = new BufferedReader(new FileReader(f1));
        int NUMBER_CITIES = 0;
        try {
            while (input1.readLine() != null) {
                NUMBER_CITIES++;
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("Количество городов: " + NUMBER_CITIES);
 
        // Чтение данных из открытого файла
        int[][] array = new int[NUMBER_CITIES][NUMBER_CITIES];
        int i = 0;
        try {
            String line;
            while ((line = input.readLine()) != null) {
                StringTokenizer st = new StringTokenizer(line);
                int j = 0;
                while (st.hasMoreTokens()) {
                    array[i][j] = Integer.parseInt(st.nextToken());
                    j++;
                }
                i++;
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        // Выполнение первого сокращения матрицы затрат
        int x = 0;
        x = reduce(array, x, 9999, 9999);
        lobject l1 = new lobject(NUMBER_CITIES);
 
        //Корень дерева начинается с города 0.
        l1.city = 0;
        l1.cost = x;
        l1.matrix = array;
        l1.st.push(0);
        l1.remainingcity = new int[NUMBER_CITIES - 1];
        l1.city_left_to_expand = NUMBER_CITIES - 1;
 
        for (int o = 0; o < NUMBER_CITIES - 1; o++) {
            l1.remainingcity[o] = o + 1;
        }
        //переменная для отслеживания количества развернутых узлов
        int count = 0;
        //Стек DS для ведения узлов в дереве
        Stack<lobject> s = new Stack<>();
        //Толкая корень в стек
        s.push(l1);
        //Временная переменная для хранения лучшего решения, найденного до сих пор
        lobject temp_best_solution = new lobject(NUMBER_CITIES);
        int current_best_cost = 100000;
        //Итерации стека, включая возврат
        // Запуск обхода дерева - обходы до тех пор, пока стек не станет пустым, т.е. все узлы были расширены
        while (!s.empty()) {
            // Инициализация переменной
            List main = new LinkedList();
            main = new ArrayList();
            lobject hell = s.pop();
            //Расширяйте стек только в том случае, если узел не является конечным узлом и если его стоимость лучше, чем лучшая на данный момент
            if (hell.city_left_to_expand == 0) {
                //Сравнивая стоимость этого узла с лучшими и обновляя при необходимости
                if (hell.cost <= current_best_cost) {
                    temp_best_solution = hell;
                    current_best_cost = temp_best_solution.cost;
                }
            } else {
                if (hell.cost <= current_best_cost) {
                    count++;
                    // Расширение последнего узла, извлеченного из стека
                    expand(main, hell);
                    //Определение порядка, в котором расширенные узлы должны быть помещены в стек
                    int[] arrow = new int[main.size()];
                    for (int pi = 0; pi < main.size(); pi++) {
                        lobject help = (lobject) main.get(pi);
                        arrow[pi] = help.cost;
                    }
                    // Сортировка узлов в порядке убывания на основе их стоимости
                    int[] tempppp = decreasing_sort(arrow);
                    for (int pi = 0; pi < tempppp.length; pi++) {
                        // Помещение узловых объектов в стек в порядке убывания
                        s.push((lobject) main.get(tempppp[pi]));
                    }
                    for (lobject lobject : s) {
                        output(lobject);
                    }
                }
            }
        }
        // Расчет времени остановки для времени выполнения
        long stop_time = System.currentTimeMillis();
        long run_time = stop_time - start_time;
 
        // Проверка, найдено ли решение
        if (temp_best_solution.st.size() == NUMBER_CITIES & temp_best_solution.cost < 9000) {
            // Стоимость печатного тура
            System.out.println();
            System.out.println("cost: " + current_best_cost);
            System.out.println();
            // Печать оптимального тура
            System.out.print("[ ");
            for (int st_i = 0; st_i < temp_best_solution.st.size(); st_i++) {
                Integer k = temp_best_solution.st.get(st_i);
                System.out.print(k + 1);
                System.out.print(" -> ");
            }
            System.out.print("1 ]");
            System.out.println();
            System.out.println();
            // Printing Running Time
            System.out.println(run_time + "ms");
            System.out.println();
            //Количество узлов, расширенных в алгоритме
            System.out.println("nodes expanded: " + count);
            System.out.println();
        } else {
            System.out.println("\nNo Solution.\n");
            // Printing Running Time
            System.out.println(run_time+ "ms");
            System.out.println();
        }
    }
 
    private static void toConsole(Stack<lobject> s) {
        StringBuilder str = new StringBuilder();
        str.append("[");
        for (lobject lobject : s) {
            str.append(toString(lobject)).append(",\n");
        }
        str.append("]");
        System.out.println(str);
    }
 
    private static void toConsole(int[][] array) {
        System.out.println(toString(array));
    }
 
    private static String toString(int[][] array) {
        StringBuilder str = new StringBuilder();
        str.append("[\n");
        for (int[] ints : array) {
            for (int anInt : ints) {
                if (anInt > 4500) {
                    str.append(9999-anInt);
                } else {
                    str.append(anInt);
                }
                str.append(",");
            }
            str.append("\n");
        }
        str.append("]");
        return str.toString();
    }
 
    public static String toString(lobject o) {
        return "lobject{" +
                "city=" + o.city +
                ", cost=" + o.cost +
                ", matrix=" + toString(o.matrix) +
                ", remainingcity=" + Arrays.toString(o.remainingcity) +
                ", city_left_to_expand=" + o.city_left_to_expand +
                ", st=" + o.st +
                '}';
    }
 
 
    /*
    Min Function - Reduced the passed array with the value passed
    Input - Array to be reduced, minimum value with which to reduce
    Return - Reduced array
    */
 
    public static int[] min(int[] array, int min) {
        // Recurse through array and reduce with the passed "min" value
        for (int j = 0; j < array.length; j++) {
            array[j] = array[j] - min;
        }
        // Return reduced array
        return array;
    }
 
    /*
    Minimum Function - Calculates the minimum value with which a matrix can be reduced
    Input - Array for which minimum value is to be calculated
    Return - Minimum value
    */
 
    public static int minimum(int[] array) {
        // Объявление по умолчанию как нечто меньшее, чем бесконечность, но выше, чем допустимые значения
        int min = 9000;
        // Рекурсивно через массив найти минимальное значение
        for (int i = 0; i < array.length; i++) {
            // Если значение действительно, т. Е. Меньше бесконечности, сбросьте мин с этим значением
            if (array[i] < min) {
                min = array[i];
            }
        }
        // Проверьте, не изменилось ли минимальное значение, то есть мы встретили бесконечный массив
        if (min == 9000) {
            // Вернуть 0 как ничто, чтобы уменьшить
            return 0;
        }
        // Иначе вернуть минимальное значение
        else {
            return min;
        }
    }
 
    /*
    lobject - класс, в котором хранятся необходимые данные
    */
 
    public static class lobject implements Cloneable {
        int city;
        int cost;
        int[][] matrix;
        int[] remainingcity;
        int city_left_to_expand;
        Stack<Integer> st;
 
        lobject(int number) {
            matrix = new int[number][number];
            st = new Stack<Integer>();
        }
    }
 
    /*
    Method to print the contents of object on screen
    Return - Void
    */
 
    public static void output(lobject l1) {
        System.out.println("============================================");
        System.out.println("============================================");
        System.out.println("This city is :" + l1.city);
        System.out.println("The node cost function:" + l1.cost);
        // Печать остальных городов
        System.out.println("The remaining cities to be expanded from this node");
        for (int h = 0; h < l1.remainingcity.length; h++) {
            System.out.print(l1.remainingcity[h]);
            System.out.print(" ");
        }
        System.out.println();
        System.out.println("The number of possible remaining expansions from this node are: " + l1.city_left_to_expand);
        System.out.println();
        System.out.println("============================================");
        System.out.println("============================================");
    }
 
    /*
    Expand - Node Expansion Function
    Input - List to return the reduced cost matrix, Object of node to be expanded
    Return - Cost of Reduction
    */
 
    public static void expand(List l, lobject o) {
        // Количество городов для прохождения
        int length = o.remainingcity.length;
        for (int i = 0; i < length; i++) {
            // Инициализация переменной
            if (o.remainingcity[i] == 0) continue;
            int cost;
            cost = o.cost;
            int city = o.city;
            Stack<Integer> st = new Stack<>();
            for (int st_i = 0; st_i < o.st.size(); st_i++) {
                Integer k = o.st.get(st_i);
                st.push(k);
            }
            st.push(o.remainingcity[i]);
            // Извлечение содержимого матрицы во временную матрицу для сокращения
            int[][] temparray = new int[o.matrix.length][o.matrix.length];
            for (int i_1 = 0; i_1 < temparray.length; i_1++) {
                for (int i_2 = 0; i_2 < temparray.length; i_2++) {
                    temparray[i_1][i_2] = o.matrix[i_1][i_2];
                }
            }
            //Добавление значения ребра (i, j) к стоимости
            cost = cost + temparray[city][o.remainingcity[i]];
            //Делая i-й ряд и j-й столбец бесконечным
            for (int j = 0; j < temparray.length; j++) {
                temparray[city][j] = 9999;
                temparray[j][o.remainingcity[i]] = 9999;
            }
            //Делая (j, 0) бесконечностью
            temparray[o.remainingcity[i]][0] = 9999;
            //Сокращение этой матрицы в соответствии с указанными правилами
            int cost1 = reduce(temparray, cost, city, o.remainingcity[i]);
            // Обновление содержимого объекта, соответствующего текущего тура по городу
            lobject finall = new lobject(o.matrix.length);
            finall.city = o.remainingcity[i];
            finall.cost = cost1;
            finall.matrix = temparray;
            int[] temp_array = new int[o.remainingcity.length];
            // Ограничение расширения в случае возврата
            for (int i_3 = 0; i_3 < temp_array.length; i_3++) {
                temp_array[i_3] = o.remainingcity[i_3];
            }
            temp_array[i] = 0;
            finall.remainingcity = temp_array;
            finall.city_left_to_expand = o.city_left_to_expand - 1;
            finall.st = st;
            l.add(finall);
        }
    }
 
    /*
    Reduce - Reduces the passed Matrix with minimum value possible
    Input - 2D Array to be reduced, Previous Step's Cost, Row to be processed, Column to be processed
    Return - Cost of Reduction
    */
 
    public static int reduce(int[][] array, int cost, int row, int column) {
        // Массивы для хранения строк и столбцов, которые будут уменьшены
        int[] array_to_reduce = new int[array.length];
        int[] reduced_array = new int[0];
        // Переменная для хранения обновленной стоимости
        int new_cost = cost;
        // Петля для уменьшения рядов
        for (int i = 0; i < array.length; i++) {
            // Если строка соответствует текущему городу, не уменьшайте
            if (i == row) continue;
            // Если строка не соответствует текущему городу, попробуйте уменьшить
            for (int j = 0; j < array.length; j++) {
                // Выбрать строку, которая будет уменьшена
                array_to_reduce[j] = array[i][j];
            }
            // Проверьте, можно ли уменьшить текущий ряд
            if (minimum(array_to_reduce) != 0) {
                // Обновление новой стоимости
                new_cost = minimum(array_to_reduce) + new_cost;
                // Уменьшение строки
                reduced_array = min(array_to_reduce, minimum(array_to_reduce));
                // Отталкивание уменьшенного ряда обратно в исходный массив
                for (int k = 0; k < array.length; k++) {
                    array[i][k] = reduced_array[k];
                }
            }
        }
        // Петля для уменьшения столбцов
        for (int i = 0; i < array.length; i++) {
            // Если столбец соответствует текущему городу, не уменьшайте
            if (i == column) continue;
            // Если столбец не соответствует текущему городу, попробуйте уменьшить
            for (int j = 0; j < array.length; j++) {
                // Выборка столбца должна быть уменьшена
                array_to_reduce[j] = array[j][i];
            }
            // Проверьте, можно ли уменьшить текущий столбец
            if (minimum(array_to_reduce) != 0) {
                // Обновление текущей стоимости
                new_cost = minimum(array_to_reduce) + new_cost;
                // Уменьшение столбца
                reduced_array = min(array_to_reduce, minimum(array_to_reduce));
                // Отталкивание уменьшенного столбца обратно в исходный массив
                for (int k = 0; k < array.length; k++) {
                    array[k][i] = reduced_array[k];
                }
            }
        }
 
        System.out.println("уменьшенные значения: \n" + toString(reduced_array));
        System.out.println("уменьшенная матрица: \n" + toString(array));
        System.out.println();
        return new_cost;
    }
 
    private static String toString(int[] reduced_array) {
        StringBuilder s = new StringBuilder();
        s.append("[");
        for (int i : reduced_array) {
            if (i > 4500) {
                s.append(9999-i);
            } else {
                s.append(i);
            }
            s.append(",");
        }
        s.append("]");
        return s.toString();
    }
 
    /*
    Decreasing Sort - сортирует переданный массив в порядке убывания и возвращает индекс
    Input - Массив для сортировки в порядке убывания
    Return - отсортированный массив
    */
 
    public static int[] decreasing_sort(int[] temp) {
        int[] y = new int[temp.length];
        // Получение содержимого массива
        for (int j = 0; j < temp.length; j++) {
            y[j] = temp[j];
        }
        int x = 0;
        // Сортировка
        for (int i = 0; i < temp.length - 1; i++) {
            if (temp[i] < temp[i + 1]) {
                x = temp[i];
                temp[i] = temp[i + 1];
                temp[i + 1] = x;
            }
        }
        int[] to_be_returned = new int[temp.length];
        int f = 0;
        // Помещение отсортированного содержимого в массив для возврата
        for (int j = 0; j < temp.length; j++) {
            for (int j1 = 0; j1 < temp.length; j1++) {
                if (temp[j] == y[j1]) {
                    to_be_returned[j] = j1;
                }
            }
        }
        return to_be_returned;
    }
}

import java.io.File;
import java.io.FileNotFoundException;
import java.text.DecimalFormat;
import java.util.*;
 
class Graph {
    private static final int M = -1;
    private static final String SYMBOL = "M";
 
    void start(String path) {
        long start = System.currentTimeMillis();
        Stack<Integer> stack = new Stack<>();
        System.out.println("Read graph to file:");
        int[][] matrix = readFile(path);
        int[][] clone = clone(matrix);
        List<Integer> v = new ArrayList<>();
        for (int i = 1; i <= matrix.length; i++) {
            v.add(i);
        }
        printMatrix(matrix);
        int count = 1;
        while (matrix.length > 1) {
            System.out.println("\n##########################################");
            System.out.println("STAGE #" + count++ + ":");
            int[] di = getMinArray(matrix, false);
            matrix = diffMatrix(matrix, di, false);
            int[] dj = getMinArray(matrix, true);
            matrix = diffMatrix(matrix, dj, true);
            System.out.println("\ndi: " + Arrays.toString(di) + ";");
            System.out.println("dj: " + Arrays.toString(dj) + ";");
            System.out.println("\nMatrix after diff:");
            printMatrix(matrix);
            matrix = getPath(matrix, stack, v);
            System.out.println("\nReduction matrix:");
            printMatrix(matrix);
            if (matrix.length == 1) {
                push(stack, v.remove(0));
            }
            System.out.print("Path now: ");
            printStack(stack);
        }
        if (!stack.empty()) {
            stack.push(stack.get(0));
        }
        System.out.println("\n##########################################");
        System.out.println("\nAnswer:");
        System.out.print("Path: ");
        printStack(stack);
        System.out.println("Sum:  " + getSum(stack, clone));
        start = System.currentTimeMillis() - start;
        System.out.printf("Spent time: %d.%s sec.;", start / 1000, new DecimalFormat("000").format(start % 1000));
    }
 
    private int[][] clone(int[][] martrix) {
        int[][] clone = new int[martrix.length][];
        int count = 0;
        for (int[] line : martrix) {
            clone[count++] = line.clone();
        }
        return clone;
    }
 
    private int getSum(Stack<Integer> stack, int[][] clone) {
        int sum = 0;
        if (!stack.empty()) {
            int v = stack.pop();
            while (!stack.empty()) {
                sum += clone[v - 1][stack.peek() - 1];
                v = stack.pop();
            }
        }
        return sum;
    }
 
    private boolean isNumber(String number) {
        return number != null && number.matches("\\d+");
    }
 
    private void printStack(Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        if (!stack.empty()) {
            for (Integer num : stack) {
                sb.append(num).append(" -> ");
            }
            sb.delete(sb.length() - 4, sb.length());
        }
        System.out.println(sb.toString());
    }
 
    private int[][] getPath(int[][] matrix, Stack<Integer> stack, List<Integer> v) {
        int indexI = 0;
        int indexJ = 0;
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (matrix[i][j] == 0) {
                    int sum = getMin(matrix, i, false, j) + getMin(matrix, j, true, i);
                    if (sum > max) {
                        max = sum;
                        indexI = i;
                        indexJ = j;
                    }
                }
            }
        }
        matrix[indexJ][indexI] = M;
        matrix = removeLineAndRow(matrix, indexI, indexJ);
        push(stack, v.get(indexI));
        push(stack, v.get(indexJ));
        v.remove(indexI);
        return matrix;
    }
 
    private void push(Stack<Integer> stack, int v) {
        if (stack.search(v) == -1) {
            stack.push(v);
        }
    }
 
    private int[][] removeLineAndRow(int[][] matrix, int indexI, int indexJ) {
        int[][] result = new int[matrix.length - 1][matrix.length - 1];
        int countI = 0;
        int countJ;
        for (int i = 0; i < matrix.length; i++) {
            if (i != indexI) {
                countJ = 0;
                for (int j = 0; j < matrix.length; j++) {
                    if (j != indexJ) {
                        result[countI][countJ++] = matrix[i][j];
                    }
                }
                countI++;
            }
        }
        matrix = result;
        return matrix;
    }
 
    private int getMin(int[][] matrix, int index, boolean row, int j) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            if (i != j) {
                int number = row ? matrix[i][index] : matrix[index][i];
                if (number != M && number < min) {
                    min = number;
                }
            }
        }
        return min;
    }
 
    private int[] getMinArray(int[][] matrix, boolean row) {
        int[] res = new int[matrix.length];
        int count = 0;
        for (int i = 0; i < matrix.length; i++) {
            res[count++] = getMin(matrix, i, row, -1);
        }
        return res;
    }
 
    private int[][] diffMatrix(int[][] matrix, int[] d, boolean row) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (matrix[i][j] != M) {
                    matrix[i][j] -= row ? d[j] : d[i];
                }
            }
        }
        return matrix;
    }
 
    private void printMatrix(int[][] matrix) {
        int length = matrix.length;
        for (int[] line : matrix) {
            System.out.print("[");
            for (int index = 0; index < length; index++) {
                System.out.print(line[index] == M ? SYMBOL : line[index]);
                if (index < length - 1) {
                    System.out.print(", ");
                }
            }
            System.out.println("]");
        }
    }
 
    private int[][] readFile(String path) {
        StringBuilder sb = new StringBuilder();
        try (Scanner read = new Scanner(new File(path))) {
            while (read.hasNextLine()) {
                String line = read.nextLine().trim();
                if (line.length() > 0) {
                    sb.append(line).append("\n");
                }
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        String[] lines = sb.toString().split("\n");
        int length = lines.length;
        int[][] matrix = new int[length][length];
        for (int i = 0; i < length; i++) {
            String[] numbers = lines[i].split("\\s+");
            for (int j = 0; j < length; j++) {
                if (i == j) {
                    matrix[i][j] = M;
                } else if (isNumber(numbers[j])) {
                    matrix[i][j] = Integer.parseInt(numbers[j]);
                }
            }
        }
        return matrix;
    }
}
 
class GraphTest {
    private static final String PATH = "input.txt";
 
    public static void main(String[] args) {
        new Graph().start(PATH);
    }
}

Read graph to file:
[M, 2, 3, 4]
[1, M, 3, 4]
[1, 2, M, 4]
[1, 2, 3, M]
 
##########################################
STAGE #1:
 
di: [2, 1, 1, 1];
dj: [0, 0, 1, 2];
 
Matrix after diff:
[M, 0, 0, 0]
[0, M, 1, 1]
[0, 1, M, 1]
[0, 1, 1, M]
 
Reduction matrix:
[M, 1, 1]
[0, M, 1]
[0, 1, M]
Path now: 1 -> 2
 
##########################################
STAGE #2:
 
di: [1, 0, 0];
dj: [0, 0, 0];
 
Matrix after diff:
[M, 0, 0]
[0, M, 1]
[0, 1, M]
 
Reduction matrix:
[M, 1]
[0, M]
Path now: 1 -> 2 -> 3
 
##########################################
STAGE #3:
 
di: [1, 0];
dj: [0, 0];
 
Matrix after diff:
[M, 0]
[0, M]
 
Reduction matrix:
[M]
Path now: 1 -> 2 -> 3 -> 4
 
##########################################
 
Answer:
Path: 1 -> 2 -> 3 -> 4 -> 1
Sum:  10
Spent time: 0.090 sec.;
Process finished with exit code 0

import com.sun.deploy.util.StringUtils;
 
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
 
class Graph {
    private static final char V = 'V';
    private static final String ELEMENT = "M";
    private static final int ELEMENT_DIAGONAL = -1;
    private static final String DI = "di";
    private static final String DJ = "dj";
 
    private List<List<Integer>> matrix;
    private final List<Integer> vi;
    private final List<Integer> vj;
 
    Graph(String path) {
        this.matrix = init(path);
        this.vi = fillV(this.matrix.size());
        this.vj = fillV(this.matrix.size());
    }
 
    private List<List<Integer>> clone(List<List<Integer>> matrix) {
        List<List<Integer>> clone = new ArrayList<>();
        for (List<Integer> sub : matrix) {
            List<Integer> temp = new ArrayList<>();
            Collections.addAll(temp, sub.toArray(new Integer[0]));
            clone.add(temp);
        }
        return clone;
    }
 
    void bfs() {
        List<String> result = new ArrayList<>();
        List<List<Integer>> clone = clone(this.matrix);
        int count = 1;
 
        while (this.matrix.size() > 0 && result.size() != clone.size()) {
            String separator = String.format(String.format("%s%d%s", "%", 100, "s"), "").replaceAll(" ", "#");
            System.out.println("\n" + separator);
 
            System.out.printf("%50s\n", "ЭТАП #" + count++);
 
            System.out.println("ГРАФ:");
            List<String> list = matrixFormatToPrint(matrixToStringList(this.matrix), null, null);
            list.forEach(System.out::println);
            System.out.println("\nИщем и считаем " + DI + ":");
            int[] di = getMinByMatrix(this.matrix, false);
            System.out.printf("%s: %s;\n\n", DI, Arrays.toString(di));
 
            List<String> matrix = matrixFormatToPrint(matrixToStringList(this.matrix), di, null);
            List<String> diff = matrixFormatToPrint(getDiffList(this.matrix, di, false), di, null);
            this.matrix = diffMatrix(this.matrix, di, false);
            List<String> matrixRes = matrixFormatToPrint(matrixToStringList(this.matrix), null, null);
            list = matrixFormatToPrintCascade(matrix, diff, matrixRes, false);
            list.forEach(System.out::println);
 
            System.out.println("\nНа данном этапе ГРАФ:");
            list = matrixFormatToPrint(matrixToStringList(this.matrix), null, null);
            list.forEach(System.out::println);
 
            System.out.println("\nИщем и считаем " + DJ + " :");
            int[] dj = getMinByMatrix(this.matrix, true);
            System.out.printf("%s: %s;\n\n", DJ, Arrays.toString(dj));
 
            matrix = matrixFormatToPrint(matrixToStringList(this.matrix), null, dj);
            diff = matrixFormatToPrint(getDiffList(this.matrix, dj, true), null, dj);
            this.matrix = diffMatrix(this.matrix, dj, true);
            matrixRes = matrixFormatToPrint(matrixToStringList(this.matrix), null, null);
            list = matrixFormatToPrintCascade(matrix, diff, matrixRes, true);
            list.forEach(System.out::println);
 
            System.out.println("\nНа данном этапе ГРАФ:");
            list = matrixFormatToPrint(matrixToStringList(this.matrix), null, null);
            list.forEach(System.out::println);
 
            System.out.println("\nИщем <оценки> нулей:");
            List<List<String>> matrixMark = new ArrayList<>();
            Pare maxZero = getMaxPare(this.matrix, matrixMark);
            list = matrixFormatToPrint(matrixMark, null, null);
            list.forEach(System.out::println);
 
            System.out.println("\nВыбираем самую большую <оценку>:");
            System.out.println(matrixMark.get(maxZero.i).get(maxZero.j));
 
            System.out.println("\nНайденный путь:");
            String vi = String.valueOf(this.vi.get(maxZero.i));
            String vj = String.valueOf(this.vj.get(maxZero.j));
            if (!result.contains(vi)) {
                result.add(vi);
            }
            if (!result.contains(vj)) {
                result.add(vj);
            }
            System.out.println(vi + " -> " + vj);
 
            System.out.println("\nУдаляем строку и столбец с наибольшей <оценкой> у нуля.");
            this.matrix.get(maxZero.j).set(maxZero.i, ELEMENT_DIAGONAL);
 
            this.matrix.remove(maxZero.i);
            for (List<Integer> sub : this.matrix) {
                sub.remove(maxZero.j);
            }
            this.vi.remove(maxZero.i);
            this.vj.remove(maxZero.j);
            list = matrixFormatToPrint(matrixToStringList(this.matrix), null, null);
            list.forEach(System.out::println);
 
            System.out.println("\nПуть на данный момент:");
            System.out.println(StringUtils.join(result, " -> "));
        }
 
        if (!result.isEmpty()) {
            result.add(result.get(0));
        }
 
        System.out.println("\nИТОГОВЫЙ ПУТЬ: " + StringUtils.join(result, " -> ") + ";");
        System.out.println("СУММА ПУТИ: " + getSum(result, clone));
    }
 
    private int getSum(List<String> path, List<List<Integer>> matrix) {
        int sum = 0;
        if (path.size() > 1) {
            int i = Integer.parseInt(path.get(0)) - 1;
            for (int index = 1; index < path.size(); index++) {
                int j = Integer.parseInt(path.get(index)) - 1;
                sum += matrix.get(i).get(j);
                i = j;
            }
        }
        return sum;
    }
 
    private Pare getMaxPare(List<List<Integer>> matrix, List<List<String>> res) {
        Pare result = new Pare(0, 0);
        int max = 0;
        for (int i = 0; i < matrix.size(); i++) {
            List<String> temp = new ArrayList<>();
            for (int j = 0; j < matrix.size(); j++) {
                int value = matrix.get(i).get(j);
                if (value == 0) {
                    Pare pare = getMin(matrix, i, j);
                    if (pare.i + pare.j > max) {
                        max = pare.i + pare.j;
                        result = new Pare(i, j);
                    }
                    temp.add("0(" + (pare.i + pare.j) + ")");
                } else if (value == ELEMENT_DIAGONAL) {
                    temp.add(ELEMENT);
                } else {
                    temp.add(String.valueOf(value));
                }
            }
            res.add(temp);
        }
        return result;
    }
 
    private Pare getMin(List<List<Integer>> matrix, int i, int j) {
        int x = Integer.MAX_VALUE;
        int y = Integer.MAX_VALUE;
        int count = 0;
        for (int value : matrix.get(i)) {
            if (count++ != j && value != ELEMENT_DIAGONAL && value < x) {
                x = value;
            }
        }
        for (count = 0; count < matrix.size(); count++) {
            if (count != i) {
                int value = matrix.get(count).get(j);
                if (value != ELEMENT_DIAGONAL && value < y) {
                    y = value;
                }
            }
        }
        x = x == Integer.MAX_VALUE ? 0 : x;
        y = y == Integer.MAX_VALUE ? 0 : y;
        return new Pare(x, y);
    }
 
    private List<List<String>> getDiffList(List<List<Integer>> matrix, int[] d, boolean dj) {
        List<List<String>> res = new ArrayList<>();
        int count = 0;
        for (List<Integer> sub : matrix) {
            List<String> temp = new ArrayList<>();
            for (int value : sub) {
                temp.add(value != ELEMENT_DIAGONAL ? value + "-" + d[count] : ELEMENT);
                if (dj) {
                    count++;
                }
            }
            res.add(temp);
            count = dj ? 0 : count + 1;
        }
        return res;
    }
 
    private int[] getMinByMatrix(List<List<Integer>> matrix, boolean dj) {
        int[] d = new int[matrix.size()];
        Arrays.fill(d, Integer.MAX_VALUE);
        int count = 0;
        for (List<Integer> list : matrix) {
            for (int value : list) {
                if (value != ELEMENT_DIAGONAL && d[count] > value) {
                    d[count] = value;
                }
                if (dj) {
                    count++;
                }
            }
            count = dj ? 0 : count + 1;
        }
        return d;
    }
 
    private List<String> matrixFormatToPrintCascade(List<String> matrix, List<String> diff, List<String> res, boolean dj) {
        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int size = res.size();
        int half = matrix.size() / 2;
        for (int index = 0; index < size; index++) {
            sb.append(matrix.get(index)).append("   ");
            sb.append(index == half ? "=>" : "  ");
            sb.append("   ");
            sb.append(diff.get(index)).append("   ");
            sb.append(index == half ? "=>" : "  ");
            sb.append("   ");
            sb.append(res.get(index));
            result.add(sb.toString());
            sb.delete(0, sb.length());
        }
        if (dj) {
            sb.append(matrix.get(matrix.size() - 2)).append("        ").append(diff.get(diff.size() - 2));
            result.add(sb.toString());
            sb.delete(0, sb.length());
            sb.append(matrix.get(matrix.size() - 1)).append("        ").append(diff.get(diff.size() - 1));
            result.add(sb.toString());
        }
        return result;
    }
 
    private int getMaxLengthG(List<List<String>> matrixString, int min) {
        int max = String.valueOf(matrixString.size()).length();
        for (List<String> sub : matrixString) {
            for (String value : sub) {
                if (value.length() > max) {
                    max = value.length();
                }
            }
        }
        return Math.max(min, max);
    }
 
    private int getMaxLengthV(List<Integer> v, int min) {
        int max = 0;
        for (int value : v) {
            if (value > max) {
                max = value;
            }
        }
        return Math.max(min, String.valueOf(max).length());
    }
 
    private List<List<String>> matrixToStringList(List<List<Integer>> matrix) {
        List<List<String>> res = new ArrayList<>();
        for (List<Integer> list : matrix) {
            List<String> strList = new ArrayList<>();
            for (int value : list) {
                strList.add(value == ELEMENT_DIAGONAL ? ELEMENT : String.valueOf(value));
            }
            res.add(strList);
        }
        return res;
    }
 
    private List<List<Integer>> diffMatrix(List<List<Integer>> matrix, int[] d, boolean dj) {
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix.get(i).size(); j++) {
                int value = matrix.get(i).get(j);
                if (value != ELEMENT_DIAGONAL) {
                    value = dj ? value - d[j] : value - d[i];
                    matrix.get(i).set(j, value);
                }
            }
        }
        return matrix;
    }
 
    private List<String> matrixFormatToPrint(List<List<String>> list, int[] di, int[] dj) {
        List<String> res = new ArrayList<>();
        int sizeV = getMaxLengthV(this.vi, Math.max(DI.length(), DJ.length()));
        sizeV = Math.max(getMaxLengthV(this.vj, Math.max(DI.length(), DJ.length())), sizeV);
        int sizeG = getMaxLengthG(list, Math.max(DI.length(), DJ.length()));
        String tabV = String.format("%s%d%s", "%", sizeV + 1, "s");
        String tabG = String.format("%s%d%s", "%", sizeG + 1, "s");
        StringBuilder sb = new StringBuilder();
        sb.append(String.format(tabV, V)).append(" |");
        for (int v : this.vj) {
            sb.append(String.format(tabG, v)).append(" ");
        }
        if (di != null && di.length > 0) {
            sb.append("|").append(String.format(tabV, DI));
        }
        String lineSeparator = String.format(String.format("%s%d%s", "%", sb.length(), "s"), "").
                replaceAll(" ", "-");
        res.add(sb.toString());
        sb.delete(0, sb.length());
        res.add(lineSeparator);
        int count = 0;
        for (List<String> sub : list) {
            sb.append(String.format(tabV, this.vi.get(count++))).append(" |");
            for (String value : sub) {
                sb.append(String.format(tabG, value));
                sb.append(" ");
            }
            if (di != null && di.length > 0) {
                sb.append("|").append(String.format(tabV, di[count - 1]));
            }
            res.add(sb.toString());
            sb.delete(0, sb.length());
        }
        if (dj != null && dj.length > 0) {
            sb.append(String.format(tabV, DJ)).append(" |");
            for (int value : dj) {
                sb.append(String.format(tabG, value)).append(" ");
            }
            if (di != null && di.length > 0) {
                sb.append("| ").append(String.format(tabG, ""));
            }
            res.add(lineSeparator);
            res.add(sb.toString());
        }
        return res;
    }
 
    private List<Integer> fillV(int size) {
        List<Integer> list = new ArrayList<>();
        for (int v = 1; v <= size; v++) {
            list.add(v);
        }
        return list;
    }
 
    private List<List<Integer>> init(String path) {
        List<List<Integer>> matrix = getMatrix(readFile(path));
        checkMatrix(matrix);
        return matrix;
    }
 
    private List<String> readFile(String path) {
        List<String> lines = new ArrayList<>();
        try (Scanner in = new Scanner(new File(path))) {
            while (in.hasNextLine()) {
                lines.add(in.nextLine().trim());
            }
        } catch (FileNotFoundException e) {
            throw new IncorrectGraphException(String.format("Файл [путь = %s] не найден.", path));
        }
        return lines;
    }
 
    private List<List<Integer>> getMatrix(List<String> list) {
        List<List<Integer>> res = new ArrayList<>();
        if (list != null) {
            int i = 0;
            for (String line : list) {
                if (!line.isEmpty()) {
                    List<Integer> temp = new ArrayList<>();
                    int j = 0;
                    for (String element : line.split("\\s+")) {
                        if (i != j++) {
                            if (isInteger(element)) {
                                temp.add(Integer.parseInt(element));
                            } else {
                                throw new IncorrectGraphException("Не корректные данные в файле.");
                            }
                        } else {
                            temp.add(ELEMENT_DIAGONAL);
                        }
                    }
                    res.add(temp);
                    i++;
                }
            }
        }
        return res;
    }
 
    private void checkMatrix(List<List<Integer>> matrix) {
        if (!matrix.isEmpty()) {
            for (List<Integer> list : matrix) {
                if (list.size() != matrix.size()) {
                    throw new IncorrectGraphException("Матрица должна иметь одинаковую выосту и ширину.");
                }
            }
        } else {
            throw new IncorrectGraphException("Файл пуст.");
        }
    }
 
    private boolean isInteger(String str) {
        return str != null && str.matches("\\d+");
    }
 
    class IncorrectGraphException extends RuntimeException {
        IncorrectGraphException(String message) {
            super(message);
        }
    }
 
    class Pare {
        private final int i;
        private final int j;
 
        Pare(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}
 
class GraphTest {
    private static final String PATH = "input.txt";
 
    public static void main(String[] args) {
        new Graph(PATH).bfs();
    }
}

####################################################################################################
                                           ЭТАП #1
ГРАФ:
  V |  1   2   3   4 
---------------------
  1 |  M   7  19   4 
  2 | 18   M   3  11 
  3 | 12   5   M   5 
  4 |  6  22   3   M 
 
Ищем и считаем di:
di: [4, 3, 5, 3];
 
  V |  1   2   3   4 | di          V |    1     2     3     4 | di          V |  1   2   3   4 
-------------------------        ---------------------------------        ---------------------
  1 |  M   7  19   4 |  4          1 |    M   7-4  19-4   4-4 |  4          1 |  M   3  15   0 
  2 | 18   M   3  11 |  3   =>     2 | 18-3     M   3-3  11-3 |  3   =>     2 | 15   M   0   8 
  3 | 12   5   M   5 |  5          3 | 12-5   5-5     M   5-5 |  5          3 |  7   0   M   0 
  4 |  6  22   3   M |  3          4 |  6-3  22-3   3-3     M |  3          4 |  3  19   0   M 
 
На данном этапе ГРАФ:
  V |  1   2   3   4 
---------------------
  1 |  M   3  15   0 
  2 | 15   M   0   8 
  3 |  7   0   M   0 
  4 |  3  19   0   M 
 
Ищем и считаем dj :
dj: [3, 0, 0, 0];
 
  V |  1   2   3   4           V |    1     2     3     4           V |  1   2   3   4 
---------------------        -----------------------------        ---------------------
  1 |  M   3  15   0           1 |    M   3-0  15-0   0-0           1 |  M   3  15   0 
  2 | 15   M   0   8           2 | 15-3     M   0-0   8-0           2 | 12   M   0   8 
  3 |  7   0   M   0    =>     3 |  7-3   0-0     M   0-0    =>     3 |  4   0   M   0 
  4 |  3  19   0   M           4 |  3-3  19-0   0-0     M           4 |  0  19   0   M 
---------------------        -----------------------------
 dj |  3   0   0   0          dj |    3     0     0     0 
 
На данном этапе ГРАФ:
  V |  1   2   3   4 
---------------------
  1 |  M   3  15   0 
  2 | 12   M   0   8 
  3 |  4   0   M   0 
  4 |  0  19   0   M 
 
Ищем <оценки> нулей:
  V |    1     2     3     4 
-----------------------------
  1 |    M     3    15  0(3) 
  2 |   12     M  0(8)     8 
  3 |    4  0(3)     M  0(0) 
  4 | 0(4)    19  0(0)     M 
 
Выбираем самую большую <оценку>:
0(8)
 
Найденный путь:
2 -> 3
 
Удаляем строку и столбец с наибольшей <оценкой> у нуля.
  V |  1   2   4 
-----------------
  1 |  M   3   0 
  3 |  4   M   0 
  4 |  0  19   M 
 
Путь на данный момент:
2 -> 3
 
####################################################################################################
                                           ЭТАП #2
ГРАФ:
  V |  1   2   4 
-----------------
  1 |  M   3   0 
  3 |  4   M   0 
  4 |  0  19   M 
 
Ищем и считаем di:
di: [0, 0, 0];
 
  V |  1   2   4 | di          V |    1     2     4 | di          V |  1   2   4 
---------------------        ---------------------------        -----------------
  1 |  M   3   0 |  0   =>     1 |    M   3-0   0-0 |  0   =>     1 |  M   3   0 
  3 |  4   M   0 |  0          3 |  4-0     M   0-0 |  0          3 |  4   M   0 
  4 |  0  19   M |  0          4 |  0-0  19-0     M |  0          4 |  0  19   M 
 
На данном этапе ГРАФ:
  V |  1   2   4 
-----------------
  1 |  M   3   0 
  3 |  4   M   0 
  4 |  0  19   M 
 
Ищем и считаем dj :
dj: [0, 3, 0];
 
  V |  1   2   4           V |    1     2     4           V |  1   2   4 
-----------------        -----------------------        -----------------
  1 |  M   3   0           1 |    M   3-3   0-0           1 |  M   0   0 
  3 |  4   M   0    =>     3 |  4-0     M   0-0    =>     3 |  4   M   0 
  4 |  0  19   M           4 |  0-0  19-3     M           4 |  0  16   M 
-----------------        -----------------------
 dj |  0   3   0          dj |    0     3     0 
 
На данном этапе ГРАФ:
  V |  1   2   4 
-----------------
  1 |  M   0   0 
  3 |  4   M   0 
  4 |  0  16   M 
 
Ищем <оценки> нулей:
  V |     1      2      4 
--------------------------
  1 |     M  0(16)   0(0) 
  3 |     4      M   0(4) 
  4 | 0(20)     16      M 
 
Выбираем самую большую <оценку>:
0(20)
 
Найденный путь:
4 -> 1
 
Удаляем строку и столбец с наибольшей <оценкой> у нуля.
  V |  2   4 
-------------
  1 |  0   M 
  3 |  M   0 
 
Путь на данный момент:
2 -> 3 -> 4 -> 1
 
ИТОГОВЫЙ ПУТЬ: 2 -> 3 -> 4 -> 1 -> 2;
СУММА ПУТИ: 21
 
Process finished with exit code 0