Поиск кратчайшего пути в графе с помощью алгоритма джонсона реферат

Обновлено: 19.05.2024

Дональд Б. Джонсон ( в )

Алгоритм , алгоритм теории графов ( d ) , задачи слежения

О ( | V | 2 бревно ⁡ | V | + | V | | E | ) \ log | V | + | V || E |)>

В информатике , алгоритм Джонсона вычисляет кратчайшие пути между всеми парами вершин в ориентированном графе , с взвешенными дугами . Веса дуг может быть отрицательным, если нет цепей с отрицательным весом. Это особенно эффективно, когда график полый . Алгоритм работает, сначала используя алгоритм Беллмана-Форда для вычисления преобразования начального графа, которое удаляет все отрицательные веса, что позволяет использовать на втором этапе алгоритм Дейкстры на преобразованном графе. Алгоритм назван в честь Дональда Б. Джонсона (in), который впервые опубликовал этот метод в 1977 году.

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

Резюме

Описание алгоритма

Алгоритм состоит из следующих шагов:

Добавьте в граф новую вершину q и соедините эту вершину дугами нулевого веса со всеми остальными узлами.
Используйте алгоритм Беллмана-Форда, начиная с новой вершины q, чтобы определить для каждой вершины v минимальный вес h ( v ) пути из q в v . Если обнаруживается отрицательный цикл, алгоритм останавливается в случае сбоя.
Перенесите дуги исходного графа, используя значения, вычисленные алгоритмом Беллмана-Форда: дуга от u до v , старый вес которой равен числу w (u, v) , имеет для нового веса положительное число w (u , v) + h (u) - h (v) .
Удалите вершину q и для любой вершины s примените алгоритм Дейкстры из источника s (затем мы можем определить кратчайшие пути от любой вершины к любой вершине в графе с новыми весами).

Пример

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

Исходный граф (слева на иллюстрации) имеет две отрицательные дуги, но не имеет отрицательного цикла. Затем мы представляем граф с новой вершиной q и дугами нулевого веса по направлению ко всем вершинам исходного графа x, y, z и w. Затем мы показываем дерево кратчайших путей, вычисленное алгоритмом Беллмана-Форда с q в качестве исходной вершины. Значения h ( v ) (выделены оранжевым цветом на чертеже), присвоенные каждому узлу, представляют собой веса кратчайших путей от q до этого узла. Все эти значения отрицательны или равны нулю, поскольку по построению q уже имеет дугу нулевого веса по направлению к каждой вершине, и более короткий путь не может быть тяжелее этой дуги. Справа представлен пересмотренный график. Он формируется заменой веса каждой дуги (u, v) на вес (u, v) + h (u) - h (v) . В этом пересмотренном графе веса дуг всегда положительны или равны нулю, а более короткий путь между двумя произвольными вершинами использует ту же последовательность дуг как более короткий путь между этими двумя вершинами в исходном графе. Алгоритм заканчивается применением алгоритма Дейкстры несколько раз для каждой из четырех начальных вершин в пересмотренном графе.

Коррекция алгоритма

Перевзвешивание обратимое

В пересмотренном графе любой путь от узла к узлу увеличивается на то же значение . s т час ( s ) - час ( т )

Действительно, либо путь от до . Его вес на пересмотренном графике равен: против знак равно ( s , п 1 , п 2 , . , п нет , т ) , p_ , \ ldots, p_ , t)> s т

Каждый термин отменяется термином в предыдущем выражении в круглых скобках. Это телескопическая сумма . Таким образом, мы получаем: + час ( п я ) )> - час ( п я ) )>

( п о я d s ( s , п 1 ) + п о я d s ( п 1 , п 2 ) + . . . + п о я d s ( п нет , т ) ) + час ( s ) - час ( т ) вес (s, p_ ) + вес (p_ , p_ ) + . + вес (p_ , t) + h (s) -h (t)> .

Выражение в скобках - это вес пути в начальном весе. Таким образом, повторное взвешивание увеличивается на одно и то же значение на каждом пути от до . час ( s ) - час ( т ) s т

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

График с повторным взвешиванием положительный

С другой стороны, все ребра взвешенного графа имеют положительный вес.

Обратите внимание, что вес кратчайшего пути от q до любой другой вершины u равен нулю в пересмотренном графе. Действительно, такой более короткий путь также является более коротким путем в исходном графе, куда мы добавили q. И по определению повторного взвешивания, взвешенный вес каждой дуги такого кратчайшего пути равен нулю. Таким образом, в перенастроенном графе для любой дуги (u, v) вес пути q → u → v равен 0 + weight (u, v). Он больше 0, потому что вес более короткого пути от q до v равен 0. Значит, дуга (u, v) имеет положительный вес.

Поскольку все ребра имеют положительный вес в пересмотренном графе, алгоритм Дейкстры выполняется правильно.

Псевдокод

Анализ сложности

Временная сложность этого алгоритма, используя кучу Фибоначчи для реализации алгоритма Дейкстры, в . Алгоритм фактически требует времени для фазы, составленной из алгоритма Беллмана-Форда, и для каждого из | V | вызовы алгоритма Дейкстры. Таким образом, когда график полый, общее время может быть меньше, чем у алгоритма Флойда-Уоршалла, который решает ту же проблему во времени . О ( | V | 2 бревно ⁡ | V | + | V | | E | ) \ log | V | + | V || E |)> О ( | V | | E | ) О ( | V | бревно ⁡ | V | ) О ( | V | 3 ) )>

Алгоритм Джонсона (англ. Johnson's algorithm) находит кратчайшие пути между всеми парами вершин во взвешенном ориентированном графе с любыми весами ребер, но не имеющем отрицательных циклов.

Содержание

В этом алгоритме используется метод изменения веса (англ. reweighting). Суть его заключается в том, что для заданного графа [math] G [/math] строится новая весовая функция [math] \omega_\varphi [/math] , неотрицательная для всех ребер графа [math] G [/math] и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой потенциальной функции.

Пусть [math] \varphi : V \rightarrow \mathbb R [/math] — произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет [math] \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) [/math] .

Такая потенциальная функция строится добавлем фиктивной вершины [math] s [/math] в [math] G [/math] , из которой проведены ориентированные ребра нулевого веса во все остальные вершины графа, и запуском алгоритма Форда-Беллмана из нее ( [math] \varphi(v) [/math] будет равно длине кратчайшего пути из [math] s [/math] в [math] v [/math] ). На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.

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

Утверждается, что если какой-то путь [math] P [/math] был кратчайшим относительно весовой функции [math] \omega [/math] , то он будет кратчайшим и относительно новой весовой функции [math] \omega_\varphi [/math] .

Пусть [math]P,\; Q [/math] — два пути [math] a \rightsquigarrow b\;[/math] и [math]\omega(P) \lt \omega(Q).[/math] Тогда [math]\forall \varphi: \; \omega_\varphi(P) \lt \omega_\varphi(Q)[/math]

В графе [math]G[/math] нет отрицательных циклов [math]\Leftrightarrow[/math] существует потенциальная функция [math] \phi:\; \forall uv \in E\; \omega_\varphi(uv) \geqslant 0 [/math]

[math]\Leftarrow [/math] : Рассмотрим произвольный [math]C[/math] — цикл в графе [math]G[/math]

По лемме, его вес равен [math] \omega(C) = \omega_\varphi(C) + \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \geqslant 0[/math]

[math]\Rightarrow [/math] : Добавим фиктивную вершину [math]s[/math] в граф, а также ребра [math] s \to u [/math] весом [math] 0 [/math] для всех [math] u [/math] .

Предварительно построим граф [math]G' = (V',\;E')[/math] , где [math]V' = V \cup \[/math] , [math]s \not\in V[/math] , а [math]E' = E \cup \[/math]

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

Алгоритм Джонсона работает за [math]O(VE + VD)[/math] , где [math]O(D)[/math] — время работы алгоритма Дейкстры. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона есть [math]O(V^2\log V + V E)[/math] . В случае реализации очереди с приоритетами в виде двоичной кучи время работы равно [math]O(V E \log V)[/math] .

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

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

В исследовании этих двух алгоритмов собственно и состоит задача курсовой работы.

2. Логико-функциональная модель алгоритма

2.1. Теоретические сведения

В математической теории графов и информатике граф — это совокупность объектов со связями между ними.

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах

Граф с шестью вершинами и семью ребрами

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

Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

· V это множество вершин или узлов,

· E это множество рёбер – связей между парами вершин.

V (а значит и E) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = .

СтепеньюdegV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Задачу составления алгоритма нахождения k кратчайших путей в графе условно можно разбить на две подзадачи:

1) Нахождение одного кратчайшего пути между двумя точками (реализуется алгоритм Дейкстры)

2) Нахождение k кратчайших путей между двумя точками (реализуется алгоритм Йена)

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

Алгоритм Дейкстры — алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием “кратчайший путь — первый” (Shortest Path First)

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

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из ещё не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.

2.3. Алгоритм Йена

Этот алгоритм предполагает, что мы умеем находить один кратчайший путь в графе.

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

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

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

3. Блок-схема алгоритма

4. Анализ сложности алгоритма

Анализ сложности и трудоемкости алгоритма заключается в выявлении того, насколько эффективно работает алгоритм и насколько сильно загружается процессор. Основным критерием в этом плане является скорость выполнения алгоритма.

Скорость выполнения можно легко измерить, используя стандартные функции языка PHP, на котором был написан алгоритм. При этом будем циклически высчитывать время, затраченное на обработку графов размерности от 3 до 19 вершин. См. рис. 1

Рис. 1 – Зависимость времени выполнения tот числа вершин n

Несложно заметить, что функция имеет вид параболы. Это означает, что с увеличением размера графа довольно резко возрастает и время выполнения. Таким образом, алгоритм будет работать эффективно с графами размером до 20 вершин. Что же касается графов с большим размером, то, к примеру, граф размером 30 вершин будет обрабатываться 195.74 секунд, то есть немногим больше 3 минут. Это не очень удобно, однако стоит заметить, что данный алгоритм тестировался на компьютере с тактовой частотой 2.02 ГГц, что не так уж много по сегодняшним меркам.

5. Разработка программы

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

5.1. Реализация алгоритма Дейкстры

Прежде всего необходимо проинициализировать матрицу данных. Матрица данных представляет собой двухмерный массив, значениями которого являются длины ребер, которые соединяют точки, являющиеся в матрице координатами по x и по y. На примере рассмотрен такой граф:

array(0, 7, 9, 0, 0, 14),

array(0, 0,10,15, 0, 0),

array(0, 0, 0,11, 0, 2),

array(0, 0, 0, 0, 6, 0),

array(0, 0, 0, 0, 0, 9),

array(0, 0, 0, 0, 0, 0)

Таким образом видно, что вес ребра, соединяющего, к примеру, 2-ю и 5-ю точки будет соответствовать значению 2-го ряда и 5-го столбца (или 5-го ряда и 2-го столбца) в матрице.

Продолжаем инициализацию: переменная $start хранит номер исходной точки (начиная с нуля), переменная $end – конечной, одномерный массив $dist – кратчайшие расстояния от исходной точки до всех остальных, а двухмерный массив $way– кратчайшие пути в графе.

Всем элементам массива $dist (кроме $dist[$start]) присваивается значение, которое будет заведомо больше длины любого пути в графе. В программе это число 1000. Элементу $dist[$start] присваивается значение 0. Также присваиваем значение первому шагу в массиве путей: $way[$start][0] = $start. Все это имеет такой вид:

for ($i = 0; $i $ways[$j][0])

После возврата первых k элементов массива $ways наш алгоритм можно считать реализованным.

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

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

Проблема состоит в том, чтобы найти кратчайшие пути между каждой парой вершин в данном взвешенном ориентированном графе, и веса могут быть отрицательными. Мы обсудили алгоритм Флойда Варшалла для этой проблемы. Временная сложность алгоритма Флойда Варшалла равна Θ (V 3 ). Используя алгоритм Джонсона, мы можем найти все пары кратчайших путей за O (V 2 log V + VE) времени. Алгоритм Джонсона использует и Дейкстру, и Беллмана-Форда в качестве подпрограмм.

Если мы применяем алгоритм кратчайшего пути Дейкстры с одним источником для каждой вершины, рассматривая каждую вершину как источник, мы можем найти все пары кратчайших путей за O (V * VLogV) времени. Таким образом, использование кратчайшего пути Дейкстры с одним источником кажется лучшим вариантом, чем Floyd Warshell , но проблема с алгоритмом Дейкстры в том, что он не работает для отрицательного веса.
Идея алгоритма Джонсона состоит в том, чтобы перевесить все ребра и сделать их положительными, а затем применить алгоритм Дейкстры для каждой вершины.

Как преобразовать данный граф в граф со всеми неотрицательными весовыми ребрами?
Можно подумать о простом подходе нахождения минимального ребра веса и добавления этого веса ко всем ребрам. К сожалению, это не работает , так как может быть разное количество ребер в различных путях ( подробнее см это для примера). Если существует множество путей от вершины u до v, то все пути должны быть увеличены на одинаковую величину, чтобы самый короткий путь оставался самым коротким в преобразованном графе.
Идея алгоритма Джонсона состоит в том, чтобы назначить вес каждой вершине. Пусть вес, назначенный вершине u, будет h [u]. Мы перевесим ребра, используя веса вершин. Например, для ребра (u, v) веса w (u, v) новый вес становится w (u, v) + h [u] — h [v]. Самое замечательное в этом переосмыслении состоит в том, что весь набор путей между любыми двумя вершинами увеличивается на одинаковую величину, и все отрицательные веса становятся неотрицательными. Рассмотрим любой путь между двумя вершинами s и t, вес каждого пути увеличивается на h [s] — h [t], все значения h [] вершин на пути от s до t взаимно компенсируют друг друга.

Как мы вычисляем значения h []? Для этой цели используется алгоритм Беллмана-Форда . Ниже приводится полный алгоритм. Новая вершина добавляется в граф и соединяется со всеми существующими вершинами. Кратчайшие значения расстояния от новой вершины до всех существующих вершин являются значениями h [].

Алгоритм:
1) Пусть заданным графом является G. Добавьте новую вершину s в граф, добавьте ребра из новой вершины во все вершины G. Пусть модифицированным графом будет G '.

2) Запустите алгоритм Беллмана-Форда на G 'с s в качестве источника. Пусть расстояния, вычисленные Беллманом-Фордом, будут h [0], h [1], .. h [V-1]. Если мы найдем отрицательный весовой цикл, то вернемся. Обратите внимание, что отрицательный весовой цикл не может быть создан новой вершиной s, поскольку у s нет ребра. Все ребра из с.

4) Удалите добавленную вершину s и запустите алгоритм Дейкстры для каждой вершины.

Как преобразование обеспечивает неотрицательный вес ребер?
Следующее свойство всегда верно для значений h [], поскольку они являются кратчайшими расстояниями.

Свойство просто означает, что кратчайшее расстояние от s до v должно быть меньше или равно кратчайшему расстоянию от s до u плюс вес ребра (u, v). Новые веса: w (u, v) + h [u] - h [v]. Значение новых весов должно быть больше или равно нулю из-за неравенства h [v] Пример:
Рассмотрим следующий график.

Мы добавляем источник s и добавляем ребра из s во все вершины исходного графа. На следующей диаграмме s равно 4.

Мы вычисляем кратчайшие расстояния от 4 до всех других вершин, используя алгоритм Беллмана-Форда. Кратчайшие расстояния от 4 до 0, 1, 2 и 3 равны 0, -5, -1 и 0 соответственно, т.е. h [] = . Как только мы получим эти расстояния, мы удалим исходную вершину 4 и перевесим ребра, используя следующую формулу. w (u, v) = w (u, v) + h [u] - h [v].

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

Сложность времени: Основными шагами в алгоритме являются алгоритм Беллмана Форда, называемый один раз, и Дейкстра, называемый V раз. Временная сложность Беллмана Форда равна O (VE), а временная сложность Дейкстры равна O (VLogV). Таким образом, общая сложность времени составляет O (V 2 log V + VE).
Временная сложность алгоритма Джонсона становится такой же, как у Флойда Варшелла, когда графы полны (для полного графа E = O (V 2 ). Но для разреженных графов алгоритм работает намного лучше, чем Флойд Варшелл .

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Читайте также: