Skip to main content

Поиск кратчайшего пути

Алгоритм Дейкстры​

В графах часто стоит задача найти кратчайший путь. Путём в теории графов называется последовательность рёбер. Два ребра могут идти одно за другим в последовательности тогда и только тогда, когда эти два ребра соединены с одной и той же вершиной. Длина пути (в теории транспортных сетей это называется метка пути) равна сумме рёбер, входящих в этот путь.

Алгоритм Дейкстры

Часто в задаче требуется найти длину кратчайшего пути. Для этого нам нужен алгоритм, преложенный в 1959 году нидерландским учёным Эдсгером Дейкстрой.

Разберём алгоритм на примере графа:

Граф

Его таблица связности имеет вид:

Таблица связности

Попробуем найти кратчайший путь из Б в Ж.

Для этого будем перебирать вершины, начиная с Б следующим образом:

В массиве distances будут лежать минимальные расстояния от стартовой точки (в нашем случае от точки Б). Соответствие элементов массива и вершин определяется также, как при построении матрицы смежности: нулевой элемент соответствует букве А, первый - букве Б, второй - В и т.д.

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

Также создадим массив логических переменных true/false, элемент с индексом i которого отвечает на вопрос завершена ли обработка вершины с этим индексом.

В вершине Б мы находимся изначально, значит, длина пути до неё равна 0. Номер текущей вершины равен 1. Дальше внутри цикла перебираем всех соседей рассматриваемой точки. Если путь через текущую вершину даёт в сумме лучший результат или мы вообще в этой точке не были, то записываем новое расстояние. В конце цикла указываем, что точка обработана командой complete[currentPoint] = true;

После этого цикла мы переходим к той вершине, которую мы ещё не обработали и при этом расстояние до неё нам уже известно и оно минимально.

Визуализация алгоритма Дейкстры

Исходный код поиска пути:

import java.util.*;

public class Example2Dijkstra {

    public static void main(String[] args) {
        // кол-во вершин графа
        int SIZE = 8;
        //       А  Б  В  Г  Д  Е  Ж  З
        int[][] m = new int[][]{
                {0, 5, 0, 2, 4, 0, 0, 0}, // А
                {0, 0, 0, 5, 0, 0, 7, 2}, // Б
                {0, 0, 0, 0, 0, 0, 0, 8}, // В
                {0, 0, 0, 0, 0, 0, 1, 0}, // Г
                {0, 0, 3, 0, 0, 0, 0, 0}, // Д
                {0, 0, 0, 0, 0, 0, 2, 0}, // Е
                {0, 0, 0, 0, 0, 0, 0, 0}, // Ж
                {0, 0, 0, 0, 0, 4, 0, 0}, // З
        };
        // названия вершин
        char[] names = {'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ж', 'З'};
        // заполняем расстояния от начальной вершины до рассматриваемой значениями -1
        int[] distances = new int[SIZE];
        Arrays.fill(distances,-1);
        // начинаем с точки Б, поэтому индекс 1
        int currentPoint = 1;
        // расстояние от точки до самой себя равно нулю
        distances[currentPoint] = 0;
        // массив флагов, закончена ли проверка для заданной точки
        boolean[] complete = new boolean[SIZE];
        // пока есть следующая точка
        while (currentPoint != -1) {
            // перебираем все вершины
            for (int i = 0; i < SIZE; i++) {
                if (i == currentPoint || complete[i])
                    continue;
                // если у текущей есть с ней ребро
                if (m[currentPoint][i] > 0) {
                    // если мы не обрабатывали вершину или новое расстояние через рассматриваемую вершину выше
                    if (distances[i] == -1 || distances[i] > distances[currentPoint] + m[currentPoint][i]) {
                        // рассчитываем новое расстояние, как сумму длины пути до текущей вершины
                        // и ребра от текущей вершины до заданной
                        distances[i] = distances[currentPoint] + m[currentPoint][i];
                    }
                }
            }
            complete[currentPoint] = true;
            // ищем следующую точку
            int nextPoint = -1;
            for (int i = 0; i < SIZE; i++) {
                // если обработка точки не завершена
                if (!complete[i])
                    // если мы уже доходили до точки и следующая точка ещё не задана или
                    // новое расстояние меньше
                    if (distances[i] > 0 && (nextPoint == -1 || distances[i] < distances[nextPoint])) {
                        nextPoint = i;
                    }
            }
            // переходим к следующей точке
            currentPoint = nextPoint;

            //    System.out.println("set cp: " + currentPoint);
        }

        // Выводим расстояние от Б до Ж
        System.out.println(distances[6]);
    }
}

Получим:

6

Пример​

Рассмотрим теперь пример

Задание

Р-09. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15. Определите, какова длина кратчайшего пути из пункта Д в пункт В. В ответе запишите целое число – так, как оно указано в таблице. Задание 2

Здесь нужно применить такой же алгоритм, но с учётом перестановок. Для этого напишем функцию findMinDistance(int start, int end, int[] arr), первые два аргумента которой - это индекс стартовой точки и точки, к которой мы ищем путь, третий аргумент - это массив, хранящий внутри себя перестановку.

С помощью этого массива мы будем получать расстояния в source представлении.

    // поиск кратчайшего пути
    static int findMinDistance(int start, int end, int[] arr) {
        // заполняем расстояния от начальной вершины до рассматриваемой значениями -1
        int[] distances = new int[SIZE];
        Arrays.fill(distances,-1);
        // упорядоченное множество, в котором будут лежать индексы вершин графа, которые
        // начинаем с точки Б, поэтому индекс 1
        int currentPoint = start;
        // расстояние от точки до самой себя равно нулю
        distances[currentPoint] = 0;
        // массив флагов, закончена ли проверка для заданной точки
        boolean[] complete = new boolean[SIZE];
        // пока есть следующая точка
        while (currentPoint != -1) {
            //   System.out.println("current: " + currentPoint + " " + names[currentPoint]);
            //   System.out.println(Arrays.toString(distances));
            // перебираем все вершины
            for (int i = 0; i < SIZE; i++) {
                if (i == currentPoint || complete[i])
                    continue;
                // если у текущей есть с ней ребро
                if (source[arr[currentPoint]][arr[i]] > 0) {
                    // если мы не обрабатывали вершину или новое расстояние через рассматриваемую вершину выше
                    if (distances[i] == -1 || distances[i] > distances[currentPoint] + source[arr[currentPoint]][arr[i]]) {
                        // рассчитываем новое расстояние, как сумму длины пути до текущей вершины
                        // и ребра от текущей вершины до заданной
                        distances[i] = distances[currentPoint] + source[arr[currentPoint]][arr[i]];
                    }
                }
            }
            complete[currentPoint] = true;
            // ищем следующую точку
            int nextPoint = -1;
            for (int i = 0; i < SIZE; i++) {
                // если обработка точки не завершена
                if (!complete[i])
                    // если мы уже доходили до точки и следующая точка ещё не задана или
                    // новое расстояние меньше
                    if (distances[i] > 0 && (nextPoint == -1 || distances[i] < distances[nextPoint]))
                        nextPoint = i;

            }
            // переходим к следующей точке
            currentPoint = nextPoint;
        }

        return distances[end];
    }

Тогда весь код теперь будет таким:

public class Example2 {

    // кол-во вершин (используется для удобства)
    static int SIZE = 7;

    // названия вершин
    static char[] names = {'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ж'};

    //      П1  П2  П3  П4  П5  П6  П7
    static int[][] source = new int[][]{
            {0, 11, 7, 5, 0, 0, 12}, // П1
            {11, 0, 0, 0, 13, 8, 14}, // П2
            {7, 0, 0, 15, 0, 10, 0}, // П3
            {5, 0, 15, 0, 0, 9, 0}, // П4
            {0, 13, 0, 0, 0, 6, 0}, // П5
            {0, 8, 10, 9, 6, 0, 0}, // П6
            {12, 14, 0, 0, 0, 0, 0}  // П7
    };
    //       А  Б  В  Г  Д  Е  Ж
    static int[][] target = new int[][]{
            {0, 1, 0, 1, 0, 0, 0}, // A
            {1, 0, 1, 1, 0, 1, 0}, // Б
            {0, 1, 0, 0, 0, 1, 0}, // В
            {1, 1, 0, 0, 1, 0, 1}, // Г
            {0, 0, 0, 1, 0, 1, 1}, // Д
            {0, 1, 1, 0, 1, 0, 1}, // Е
            {0, 0, 0, 1, 1, 1, 0}  // Ж
    };

    // степени вершин
    static int[] sourceSum = new int[SIZE];
    static int[] targetSum = new int[SIZE];

    static int findMinDistance(int start, int end, int[] arr) {
        // заполняем расстояния от начальной вершины до рассматриваемой значениями -1
        int[] distances = new int[SIZE];
        Arrays.fill(distances,-1);
        // упорядоченное множество, в котором будут лежать индексы вершин графа, которые
        // начинаем с точки Б, поэтому индекс 1
        int currentPoint = start;
        // расстояние от точки до самой себя равно нулю
        distances[currentPoint] = 0;
        // массив флагов, закончена ли проверка для заданной точки
        boolean[] complete = new boolean[SIZE];
        // пока есть следующая точка
        while (currentPoint != -1) {
            // перебираем все вершины
            for (int i = 0; i < SIZE; i++) {
                if (i == currentPoint || complete[i])
                    continue;
                // если у текущей есть с ней ребро
                if (source[arr[currentPoint]][arr[i]] > 0) {
                    // если мы не обрабатывали вершину или новое расстояние через рассматриваемую вершину выше
                    if (distances[i] == -1 || distances[i] > distances[currentPoint] + source[arr[currentPoint]][arr[i]]) {
                        // рассчитываем новое расстояние, как сумму длины пути до текущей вершины
                        // и ребра от текущей вершины до заданной
                        distances[i] = distances[currentPoint] + source[arr[currentPoint]][arr[i]];
                    }
                }
            }
            complete[currentPoint] = true;
            // ищем следующую точку
            int nextPoint = -1;
            for (int i = 0; i < SIZE; i++) {
                // если обработка точки не завершена
                if (!complete[i])
                    // если мы уже доходили до точки и следующая точка ещё не задана или
                    // новое расстояние меньше
                    if (distances[i] > 0 && (nextPoint == -1 || distances[i] < distances[nextPoint]))
                        nextPoint = i;

            }
            // переходим к следующей точке
            currentPoint = nextPoint;
        }

        return distances[end];
    }

    // получить обратную перестановку
    static int[] getReversePermutation(int[] arr) {
        int[] reverse = new int[arr.length];
        for (int i = 0; i < SIZE; i++) {
            reverse[arr[i]] = i;
        }
        return reverse;
    }

    // обработка перестановки
    static void processPermutation(int[] arr) {
        // проверяем, что в представлениях совпадают степени вершин
        for (int i = 0; i < SIZE; i++) {
            if (sourceSum[arr[i]] != targetSum[i]) {
                return;
            }
        }

        // нужна проверка связности, т.е. того, что при перестановке все связи сохраняются, те не
        // обратятся в ноль
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                // если в эталонном представлении связь между вершинами есть,
                // а в данном в задании - нет
                if (target[i][j] > 0 && source[arr[i]][arr[j]] == 0)
                    // заканчиваем выполнение обработчика, потому такая перестановка
                    // создаёт представление, не совместимое с данным, а значит, нас не
                    // интересует
                    return;
            }
        }
        // здесь мы уже выполняем проверку, определённую заданием

        int minAGDistance = findMinDistance(0, 6, arr);
        // если расстояние ГД меньше ГЕ, то комбинация нам подходит
        if (minAGDistance <= 15) {
            // получаем обратную перестановку
            int[] reverse = getReversePermutation(arr);
            // выводим названия вершин
            for (int i = 0; i < SIZE; i++) {
                System.out.print(names[reverse[i]] + " ");
            }
            System.out.println();
            System.out.println(findMinDistance(4, 2, arr));
        }

    }

    // поменять местами элементы массива arr с индексами l и r
    public static void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }


    // функция-генератор перестановок
    static void permute(int[] p, int pos) {
        // Если мы дошли до последнего элемента
        if (pos == SIZE - 1) {
            processPermutation(p);
        } else { // иначе
            // Перебираем все оставшиеся элементы
            for (int i = pos; i < SIZE; i++) {
                // меняем местами текущий элемент и перебираемый
                swap(p, pos, i);
                // Вызываем Рекурсию для следующего элемента
                permute(p, pos + 1);
                // меняем местами обратно
                swap(p, pos, i);
            }
        }
    }

    // главный метод программы
    public static void main(String[] args) {
        // рассчитываем взвешенные степени
        for (int i = 0; i < SIZE; i++) {
            sourceSum[i] = 0;
            targetSum[i] = 0;
            for (int j = 0; j < SIZE; j++) {
                // в исходном представлении надо не забыть заменить ненулевые веса единицей
                sourceSum[i] += Math.signum(source[i][j]);
                targetSum[i] += target[i][j];
            }
        }
        // запускаем генерацию перестановок
        permute(new int[]{0, 1, 2, 3, 4, 5, 6}, 0);
    }

}

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

Е Б Д Ж А Г В
19

Путь с ограничениями​

Иногда попадаются задачи, где нужно найти кратчайший путь, на который наложены некоторые ограничения.

Задание

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам. Задание 6

Если путь должен обязательно пройти через заданную точку, мы просто найдём кратчайший путь от начальной до заданной, а потом от заданной до конечной. Итоговый путь и будет самым коротким. А чтобы путь не проходил через заданную вершину, нужно просто в цикле поиска соседей в алгоритме Дейкстры её пропускаем.

import java.util.Arrays;

public class Example6 {
    // кол-во вершин графа
    static int SIZE = 6;
    //       A  B  C  D  E  F
    static int[][] m = new int[][]{
            {0, 2, 4, 8, 0, 16}, // A
            {2, 0, 0, 3, 0, 0}, // B
            {4, 0, 0, 3, 0, 0}, // C
            {8, 3, 3, 0, 5, 3}, // D
            {0, 0, 0, 5, 0, 5}, // E
            {16, 0, 0, 3, 5, 0}, // F
    };

    static int findMinDistance(int start, int end, int skipPoint) {
        // заполняем расстояния от начальной вершины до рассматриваемой значениями -1
        int[] distances = new int[SIZE];
        Arrays.fill(distances,-1);
        // начинаем с точки Б, поэтому индекс 1
        int currentPoint = start;
        // расстояние от точки до самой себя равно нулю
        distances[currentPoint] = 0;
        // массив флагов, закончена ли проверка для заданной точки
        boolean[] complete = new boolean[SIZE];
        // пока есть следующая точка
        while (currentPoint != -1) {
            // перебираем все вершины
            for (int i = 0; i < SIZE; i++) {
                if (i == currentPoint || i == skipPoint || complete[i])
                    continue;
                // если у текущей есть с ней ребро
                if (m[currentPoint][i] > 0) {
                    // если мы не обрабатывали вершину или новое расстояние через рассматриваемую вершину выше
                    if (distances[i] == -1 || distances[i] > distances[currentPoint] + m[currentPoint][i]) {
                        // рассчитываем новое расстояние, как сумму длины пути до текущей вершины
                        // и ребра от текущей вершины до заданной
                        distances[i] = distances[currentPoint] + m[currentPoint][i];
                    }
                }
            }
            complete[currentPoint] = true;
            // ищем следующую точку
            int nextPoint = -1;
            for (int i = 0; i < SIZE; i++) {
                // если обработка точки не завершена
                if (!complete[i])
                    // если мы уже доходили до точки и следующая точка ещё не задана или
                    // новое расстояние меньше
                    if (distances[i] > 0 && (nextPoint == -1 || distances[i] < distances[nextPoint])) {
                        nextPoint = i;
                    }

            }
            // переходим к следующей точке
            currentPoint = nextPoint;
        }
        return distances[end];
    }

    public static void main(String[] args) {
        int part1 = findMinDistance(0, 4, 1);
        int part2 = findMinDistance(4, 5, 1);
        System.out.println(part1 + part2);
    }
}

Получим:

17