Skip to main content

Кол-во путей

В некоторых задачах от нас требуется найти не кратчайший путь, а количество путей, удовлетворяющих заданному критерию. Рассмотри пример

Задание

Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.

Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населен-ных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.

Задание 7

Решается задача так: в main мы запускаем рекуррентную процедуру, которая принимает в качестве аргументов стартовую вершину, конечную и массив положений вершин в пути. Идея заключается в том, что элементы этого массива изначально все равны -1, кроме элемента, соответствующего начальной вершине. В этой ячейке лежит ноль, потому что начальная точка первая в пути и имеет порядковый индекс 0. Индексация начинается с нуля для удобства. Это поможет нам потом в заполнении массива перестановки. Дополнительно к заданию мы найдём длины удовлетворяющих условию путей.

import java.util.Arrays;

public class Example7 {
    // названия вершин
    static char[] names = {'A', 'B', 'C', 'D', 'E', 'F', 'Z'};
    // кол-во вершин графа
    static int SIZE = 7;
    //       A  B  C  D  E  F  Z
    static int[][] m = new int[][]{
            {0, 4, 6, 0, 0, 0, 30}, // A
            {0, 0, 3, 0, 0, 0, 0}, // B
            {0, 0, 0, 11, 0, 0, 27}, // C
            {0, 0, 0, 0, 4, 7, 10}, // D
            {0, 0, 0, 0, 0, 4, 8}, // E
            {0, 0, 0, 0, 5, 0, 2}, // F
            {29, 0, 0, 0, 0, 0, 0}, // Z
    };

    // кол-во путей
    static int pathCnt = 0;

    // сгенерировать пути
    static void generatePaths(int currentPoint, int target, int[] inPathPositions, int stepCnt) {
        // если мы дошли до целевой вершины
        if (currentPoint == target) {
            // шагов всегда меньше на 1, чем вершин в пути, поэтому сравниваем
            // пятью вместо шести
            if (stepCnt >= 5) {
                // инициализируем массив порядковых номеров вершин
                int[] pointOrder = new int[SIZE];
                Arrays.fill(pointOrder,-1);
                // перебираем вершины
                for (int i = 0; i < SIZE; i++) {
                    // если порядковый номер вершины в пути задан
                    if (inPathPositions[i] != -1)
                        // порядковый номер вершины
                        pointOrder[inPathPositions[i]] = i;
                }
                // находим, сколько вершин мы использовали при построении пути
                int realSize = SIZE;
                for (int i = SIZE - 1; i > 0; i--) {
                    if (pointOrder[i] != -1) {
                        realSize = i+1;
                        break;
                    }
                }

                // находим длину пути
                int pathLength = 0;
                for (int i = 0; i < realSize-1; i++) {
                    pathLength += m[pointOrder[i]][pointOrder[i + 1]];
                }
                System.out.print(pathLength + ": ");
                // выводим вершины, которые участвую в пути в порядке следования
                for (int i = 0; i < realSize; i++) {
                    System.out.print(names[pointOrder[i]]);
                }
                System.out.println();
                // увеличиваем кол-во путей на 1
                pathCnt++;
            }
        } else { // иначе
            // перебираем все вершины
            for (int i = 0; i < SIZE; i++) {
                // если порядковый номер вершины в пути ещё не задан
                // и между обрабатываемой вершиной и перебираемой есть ребро
                if (inPathPositions[i] == -1 && m[currentPoint][i] > 0) {
                    // получаем копию порядковых номеров массива
                    int[] copyInPathPositions = Arrays.copyOf(inPathPositions, SIZE);
                    // задаём порядковый номер для перебираемой вершины
                    copyInPathPositions[i] = stepCnt + 1;
                    // генерируем путь через эту вершину
                    generatePaths(i, target, copyInPathPositions, stepCnt + 1);
                }
            }
        }
    }

    // главный метод программы
    public static void main(String[] args) {
        // положение вершин в пути
        int[] inPathPositions = new int[SIZE];
        // все вершины изначально не участвуют в пути
        Arrays.fill(inPathPositions,-1);
        // начальная точка A
        int start = 0;
        // конечная точка Z
        int target = 6;
        // текущая точка имеет нулевой порядковый индекс
        inPathPositions[start] = 0;
        // ищем все пути между двумя точками
        generatePaths(start, target, inPathPositions, 0);
        // выводим ответ
        System.out.println("path cnt: " + pathCnt);
    }
}

На выходе получим:

28: ABCDEFZ
30: ABCDEZ
38: ABCDFEZ
27: ABCDFZ
27: ACDEFZ
37: ACDFEZ
path cnt: 6

Т.е. ответ на вопрос задачи: 6 путей