Краткий обзор алгоритмов для нахождения путей в графе

В настоящее время тяжело переоценить важность для прикладных задач такого раздела математики как теория графов. Графы используются в экономике, социологии, медицине, составлении расписаний и много где еще. Одним из самых важных применений графов является их применение для решения различных задач транспортировки: нахождение оптимального маршрута между двумя пунктами (в том числе нахождение оптимальных циклов), нахождение альтернативных маршрутов и т.д. Еще в 20 веке людям приходилось работать с большими объемами данных, с которыми даже группа из нескольких человек справится не в состоянии, поэтому разработка алгоритмов для решения таких задач с помощью компьютеров стала одной из актуальных проблем математики. В итоге было разработано множество алгоритмов, в том числе и для нахождения различных путей в графах. Сейчас мы рассмотрим основные из них. Данный материал будет полезен для тех, кто только знакомится с теорией графов. Для дальнейшего ознакомления рекомендую книгу Э. Майника «Алгоритмы оптимизации на сетях и графах» или книгу Б. Корте, Й. Фиген «Комбинаторная оптимизация: теория и алгоритмы».

Предполагается, что читатель знаком с базовыми понятиями теории графов. Небольшое уточнение: простой путь в графе – это набор вершина_1, ребро_1, вершина_2, ребро_2, …, вершина_n, где ребро_i – это ребро между вершиной_i и вершиной_i+1, при этом ни одна вершина и ни одно ребро в наборе не повторяются. Также предполагается что вершины графа занумерованы натуральными числами от 1 до V.

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

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

Описание работы алгоритма: в начале работы алгоритма рассматриваются все вершины, смежные с начальной вершиной искомых путей. Среди них выбирается вершина, расстояние до которой минимально (если таких вершин несколько, то выбирается любая из них). Для остальных вершин запоминается расстояние до них от начальной вершины (если есть вершины не смежные с начальной, то расстояние до них условно полагается равным плюс бесконечности). Затем для выбранной на предыдущем шаге вершины выполняется следующая процедура: для всех вершин графа кроме начальной вершины пути и текущей вершины происходит пересчет расстояний до них, а именно сравнивается запомненное на предыдущем шаге расстояние до каждой из вершин с суммой (расстояние от начальной вершины до текущей вершины + вес ребра, инцидентного текущей вершине и вершине, для которой идет перерасчет расстояний). Среди этих двух чисел выбирается наименьшее и запоминается как новое расстояние до данной вершины. Если текущая вершина не смежна с какой-то из вершин графа, то расстояние до этой вершины не изменяется. Далее снова выбирается вершина, расстояние до которой минимально, и процесс повторяется. Таким образом алгоритм продолжает работать до тех пор, пока не будут рассмотрены все вершины графа. Если требуется найти кратчайший простой путь до какой-то одной вершины, то алгоритм останавливается в тот момент, когда эта вершина выбирается в качестве вершины, расстояние до которой наименьшее.

Минусы алгоритма: все веса ребер должны быть неотрицательными числами, иначе алгоритм может сработать некорректно.

Сложность алгоритма: O(V^2)

2. Алгоритм Флойда

Алгоритм Флойда предназначен для поиска кратчайших простых путей от каждой из вершин графа до всех остальных вершин (аналогичный результат можно получить, если для каждой из вершин графа применить алгоритм Дейкстры для поиска всех кратчайших простых путей).

Описание работы алгоритма: запоминать информацию о всех кратчайших простых путях проще всего в виде матрицы размера VxV. Изначально эта матрица будет представлять собой матрицу смежности графа, т.е. элемент с номером i,j в этой матрице будет равен весу ребра между вершинами с номерами i и j или плюс бесконечности, если такого ребра нет. Далее при помощи динамического программирования происходит нахождение всех кратчайших простых путей. На нулевом шаге мы по сути рассмотрели все простые пути, в которых не разрешается иметь промежуточных вершин между начальной и конечной. На первом шаге мы разрешим иметь вершину с номером 1 в качестве промежуточной, на втором шаге – вершины с номерами 1 и 2, на последнем шаге – все вершины графа. Как происходит перерасчет длин путей: элемент новой матрицы с номером i,j равен минимуму среди элемента с номером i,j в старой матрице и среди всех сумм a_(i,k)+a_(k,j) для всех k от 1 до V. За V итераций мы получим матрицу с кратчайшими расстояниями. Остается восстановить сами простые пути. Будем также хранить матрицу A предшественников для каждой из вершин: в этой матрице элемент равен 0, если кратчайший путь между вершинами i и j не проходит через промежуточные вершины, иначе он равен предшественнику вершины j на кратчайшем простом пути из i. Если мы обновили значение в матрице расстояний при прохождении пути через вершину с номером k, то соответствующий элемент в матрице A меняется на a_(k,j). Тем самым мы вместе с длинами кратчайших простых путей получим и сами кратчайшие простые пути.

Минусы алгоритма:

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

2) Если в графе есть отрицательный цикл, то алгоритм не будет работать. Но можно ввести модификацию, которая определяет наличие отрицательного цикла в графе.

Сложность алгоритма: О(V^3). Если V раз применить алгоритм Дейкстры, то мы получим тот же результат и сложность будет такой же, но алгоритм Дейкстры не работает на графах с отрицательными весами, а для алгоритма Флойда это не проблема.

3. Поиск в глубину

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

Описание работы алгоритма: в общем случае выбирается произвольная начальная вершина (в зависимости от цели применения может быть выбрана специальная вершина). Выбранная вершина добавляется в список рассмотренных вершин. Рассматриваются все смежные с ней вершины, и выбирается вершина с наименьшим номером, (вообще говоря выбирается произвольная вершина, которая смежна с выбранной и которой нет в списке рассмотренных, но для определенности можно, например, выбирать вершину с наименьшим номером). Новая выбранная вершина также добавляется в список рассмотренных вершин, и для нее повторяется та же процедура: выбирается вершина с наименьшим номером смежная ей, которой нет в списке рассмотренных вершин. Как только у выбранной вершины нет смежных с ней вершин, которых нет в списке рассмотренных, мы возвращаемся в вершину, которая была рассмотрена до данной. Если у нее также нет смежных вершин, которые еще не были рассмотрены, то возвращаемся еще на одну вершину назад. Алгоритм завершает работу, когда не найдется не рассмотренных вершин, смежных с рассмотренными (именно так и проверяется граф на связность: если рассмотрены не все вершины графа, но нет не рассмотренных, которые были бы смежны с рассмотренными, то граф не связен).

Сложность алгоритма: О(V+E).

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

Источник: vk.com

Комментарии: