Поиск на графе k путей минимальной суммарной длины

Галочкин Владимир Иванович кандидат технических наук доцент, кафедра информатики и системного программирования, Поволжский государственный технологический институт 424000, Россия, Республика Марий Эл, г. Йошкар-Ола, пр. Ленина, 3 Galochkin Vladimir Ivanovich PhD in Technical Science Associate Professor, Department of Computer Science and System Programming, Volga State Technological Institute 424000, Russia, respublika Marii El, g. Ioshkar-Ola, ul. Pr. Lenina, 3 vigaloch@mail.ru Другие публикации этого автора

Одной из наиболее распространенных задач на графах является поиск кратчайших путей между заданными вершинами. Наиболее популярный алгоритм Дейкстры ^{[1, 2, 4, 5]} позволяет находить кратчайшие пути от заданной вершины до всех остальных вершин в случае неотрицательных весов дуг.

Поиск k кратчайших непересекающихся путей реализуется путем запрета всех вершин найденных путей и повторения поиска кратчайшего пути. Алгоритм Йена ^[3] определяет k кратчайших путей, отличающихся хотя бы одной дугой. Второй путь находится сравнением кратчайших путей при последовательном исключении из графа дуг минимального пути. Этот же принцип используется при поиске последующих путей. Другим подходом к решению данной задачи является метод двойного поиска ^{[4, 5]}.

В настоящей статье рассматривается задача поиска на взвешенном ориентированном графе k непересекающихся путей минимальной суммарной длины из заданной начальной вершины во все остальные вершины при неотрицательных весах дуг. Эта задача может ставиться, например, при изначальном планировании резервных путей между вершинами.

Рассмотрим сначала случай поиска двух путей минимальной суммарной длины из некоторой вершины s в остальные вершины.

Убедимся, что нельзя использовать «жадный» алгоритм, то есть найти лучший путь, затем удалить из графа вершины этого пути вместе с инцидентными дугами и снова найти лучший путь. Рассмотрим граф, представленный на рис. 1.

Рис. 1. Контрпример для «жадного» алгоритма

Найдем два пути минимальной суммарной длины из вершины 1 в вершину 2. Кратчайший путь 1 – 3 – 4 – 2 имеет длину 6. Следующий кратчайший путь 1 – 2 имеет длину 12. Суммарная длина составляет 18. Однако лучший вариант из путей 1 – 3 – 2 и 1 – 4 – 2 имеет общую длину 16.

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

Неявный граф состоит из n² пар. В каждой паре, кроме пар из двух начальных и двух конечных вершин, окажутся разные вершины, так как пути не должны пересекаться.

Дуга из некоторой первой пары вершин в какую-либо вторую пару описывается следующими правилами:

· в исходном графе есть дуга d, соединяющая одну из вершин первой пары с одной из вершин второй пары;

· две другие вершины из этих пар совпадают;

· весом дуги между парами вершин является вес дуги d.

В приведенном примере дуга (1, 1) – (1, 4) имеет вес 5, а дуга (3, 4) – (2, 4) вес 6. Задача сводится к нахождению в неявном графе кратчайших путей из вершины (s, s) в каждую из вершин типа (t, t).

Необходимым дополнительным требованием является отсутствие пересечения двух путей. Это означает, что на каждом шаге продолжение пути дугой (a, b) – (b, c) корректно, если вершина c не присутствует в обоих путях, восстановленных в обратном направлении от вершины (b, c) к вершине (s, s). Исключением является случай b = c, когда дуга (a, b) – (b, c) является последней на пути из вершины (s, s) в вершину (b, b).

Поскольку веса дуг неявного графа неотрицательны, то удобно модифицировать алгоритм Дейкстры ^[2]. Cначала исходная вершина получает постоянную метку 0, а остальные вершины – временные метки ∞. Потом в цикле от вершины i, получившей постоянную метку с_i последней, корректируются временные метки каждой допустимой для продолжения соответствующего пути j-ой вершины по правилу

d_j = min (d_j, c_i + a_ij),

где a_ij – вес дуги из i-ой вершины в j-ю. Следующей постоянной меткой становится наименьшая из временных меток. Процесс заканчивается, когда на очередном шаге все конечные вершины будут иметь постоянные метки либо новой постоянной метки не появится.

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

Вершины (i, j) и (j, i) имеют один смысл, поэтому можно считать, что они склеиваются и первой в паре располагается вершина с меньшим номером.

Таблица 1. Пример поиска двух путей минимальной суммарной длины

Сначала постоянная метка вершины (1, 1) получает нулевое значение, и от этой вершины пересчитываются временные метки остальных вершин неявного графа.

На шаге 2 пересчитываются временные метки от вершины (1, 3) с постоянной меткой 2. Дуга неявного графа (1, 3) – (3, 3) должна быть запрещена. Иначе оба пути состояли бы из одной и той же дуги 1 – 3. Эта ситуация является особым случаем. В других случаях достаточно контролировать отсутствие пересечения по общим вершинам путей.

На шаге 3 пересчитываются временные метки от вершины (1, 4) с постоянной меткой 3. Дуга неявного графа (1, 4) – (3, 4) запрещена. В противном случае восстановленный в обратном направлении путь (1, 1) – (1, 3) – (1, 4) – (3, 4) имел бы повторяющуюся вершину 3. Поэтому вершина (2, 4) не получает меньшей временной метки 5(1, 4).

На шаге 4 пересчитываются временные метки от вершины (1, 2) с постоянной меткой 6. Дуга неявного графа (1, 2) – (2, 3) запрещена. Иначе восстановленный в обратном направлении путь (1, 1) - (1, 3) – (1, 4) – (1, 2) – (2, 3) снова имел бы повторяющуюся вершину 3. Поэтому вершина (2, 3) не получает меньшей временной метки 8(1, 2).

На этом же шаге дуга неявного графа (1, 2) – (2, 4) также не должна использоваться. В противном случае восстановленный в обратном направлении путь (1, 1) – (1, 3) – (1, 4) – (1, 2) – (2, 4) имел бы повторяющуюся вершину 4. Поэтому вершина (2, 4) не получает меньшей временной метки 11(1, 2).

На шаге 6 вершина (4, 4) получает постоянную метку 8(1,4). Однако эта метка не может участвовать в расчете временных меток. В противном случае два пути имели бы общую вершину 4.

На шаге 7 пересчитываются временные метки от вершины (2, 3) с постоянной меткой 10. Дуга неявного графа (2, 3) – (2, 4) должна быть запрещена. В противном случае восстановленный в обратном направлении путь (1, 1) – (1, 3) – (3, 4) – (2, 3) – (2, 4) имел бы повторяющуюся вершину 4. Поэтому вершина (2, 4) не получает меньшей временной метки 11(2, 3).

Алгоритм прекращает работу после того, как все вершины типа (i, i) получат постоянные метки либо на очередном шаге новых постоянных меток не появится.

Минимальным путем из вершины (1, 1) в вершину (2, 2) является путь (1, 1) – (1, 3) – (3, 4) – (2, 3) – (2, 2), который соответствует двум непересекающимся путям 1 – 3 – 2 и 1 – 4 – 2 в исходном графе суммарной длины 16.

Двух разных путей из вершины (1, 1) в вершину (3, 3) не существует.

Наконец, минимальным путем из вершины (1, 1) в вершину (4, 4) является путь (1, 1) – (1, 3) – (1, 4) – (4, 4), который соответствует двум непересекающимся путям 1 – 3 – 4 и 1 – 4 в исходном графе суммарной длины 8.

Оценим сложность приведенного алгоритма. В неявном графе n² вершин, из которых используются n (n + 1) / 2. На каждом шаге перед вычислением временной метки проверяется допустимость соответствующей дуги по предыдущим вершинам пути с тем, чтобы исключить пересечение путей. С учетом квадратичной сложности алгоритма Дейкстры может показаться, что общая сложность алгоритма составит O(n⁵). В случае рациональной организации данных это не так.

Неявный граф является разреженным, поскольку каждая вершина в паре имеет не более n – 1 преемника. Для быстрого поиска дуг целесообразно организовать исходный граф на основе списков смежности ^[2]. Использование бинарной кучи ^[2] для хранения временных меток позволяет уменьшить объем вычислений. Наконец, на каждом шаге достаточно один раз восстановить в обратном порядке два пути из вершины (s, s) в вершину с постоянной меткой, проставляя в битовом массиве признаки запрета вершинам этих двух путей. Этот массив можно многократно использовать при вычислении временных меток допустимых вершин на данном шаге.

Общее количество шагов оценивается величиной O(n²). На каждом шаге восстановление двух путей из начальной вершины в вершину с постоянной меткой имеет сложность O(n). Далее на шаге пересчитываются временные метки только тех вершин, в которые есть дуги. Таких вершин не более 2(n-1), а допустимость дуг проверяется с помощью битового массива за константное время. Операции по изменению бинарной кучи имеют сложность O(log n), а минимальное значение выбирается из вершины кучи. В результате общая оценка сложности составит O(n³log n).

Неявный граф не нужно представлять в памяти с помощью каких-либо структур данных. Тем не менее, число временных и постоянных меток соответствует количеству используемых вершин, поэтому затраты памяти оцениваются величиной O(n²).

Рассмотрим общий случай k ≥ 2. Неявный граф строится аналогично. Его вершинами будут k-мерные вектора, координатами которых являются вершины исходного графа. Общее количество вершин составляет n^k.

Дуга (a₁, a₂, … , a_i, … , a_k) – (a₁, a₂, …, c, … , a_k) имеет вес дуги исходного графа (a_i, c). Вершина неявного графа имеет не более k(n-1) выходящих дуг, поэтому граф разреженный.

На каждом шаге восстановление k путей в направлении от вершины с постоянной меткой в начальную вершину имеет сложность O(kn). Как и ранее, допустимость дуг проверяется с помощью битового массива за константное время. Операции с бинарной кучей на каждом шаге пропорциональны величине kn×log n.

В практических целях и по вычислительным возможностям интерес представляют небольшие значения k. В этом случае корректно считать значение k константой, что дает оценку сложности O(n^k+1log n). Необходимые затраты памяти оцениваются как O(n^k).

В процессе расстановки меток имеет смысл склеивать вершины неявного графа, состоящие из одинакового множества координат, что уменьшает количество вершин и соответственно шагов алгоритма. Например, все k! вершин с некоторым множеством попарно различных координат будут считаться единственной вершиной.

Если вершина (a₁, a₂, … , a_k) неявного графа имеет одинаковые координаты ai = aj = a, то дальнейший поиск дуг исходного графа из вершины a не имеет смысла, поскольку будет пересечение путей по вершине a. Однако для продолжения поиска пути в вершину (a, a, … , a) запрета остальных отличных от a вершин быть не должно.

С другой стороны, должны быть запрещены те вершины графа (a₁, a₂, … , a_k), для которых a_i = a_j, a_s = a_t, a_i ≠ a_s. Действительно, если a_i = a_j = a, то корректный путь должен приводить в вершину (a, a, … , a). Если же a_s = a_t ≠ a, то два восстановленных пути в исходном графе пересекутся по общей вершине a_s.

Количество используемых вершин неявного графа после склеивания определяется выражением

Здесь каждое слагаемое соответствует количеству k-мерных векторов, у которых одна из n координат повторяется i раз, а остальные k – i координат отличны от нее и попарно различны. Удобно располагать номера вершин в k-мерном векторе по неубыванию.

Выполнена программная реализация описанного алгоритма. Для проверки эффективности в процессе тестирования генерировались полные графы с такими значениями весов дуг, при которых пути минимальной суммарной длины состояли из большого числа дуг. Вершины нумеровались от 1 до n. В одном из тестов вес каждой дуги (i, j) при |i - j| = 2 считался равным 2, дуги в обоих направлениях между вершинами 1 и 2 и вершинами n – 1 и n получили веса 1, а остальные дуги имели веса 10⁴. При k = 2 и начальной вершине 1 подобное задание весов приводит к нахождению путей с большим количеством дуг. Например, при n = 1000 и конечной вершине 1000 были найдены пути 1 – 2 – 4 – 6 – 8 –...– 998 – 1000 и 1 – 3 – 5 – 7 – 9 –...– 999 – 1000, то есть каждый путь состоял из 501 вершины. Программа работала менее 10 секунд на процессоре Intel Core i5-4440 с тактовой частотой 3.1 ГГц.

В другом тесте веса дуг (i, j) при |i - j| = 3 полагались равными 2, первые три вершины связывались между собой дугами весом 1, как и три последние вершины. Все остальные дуги получили вес 1000. При k = 3 и начальной вершине 1 находятся пути с большим количеством дуг. Так при n = 200 и конечной вершине 200 были найдены пути 1 – 4 – 7 – …– 196 – 199 – 200, 1 – 2 – 5 – 8 –…– 194 – 197 – 200 и 1 – 3 – 6 – … – 195 – 198 – 200, состоящие в сумме из 203 вершин. Программа работала менее 20 секунд.

Время работы программы на этих и других тестах не противоречит приведенным оценкам сложности алгоритма.

Эквивалентной задачей является поиск из начальной вершины в каждую из остальных вершин k непересекающихся путей, у которых наименьший вес дуг максимален. Подобная задача для случая двух путей рассматривалась в ^[6].