Алгоритм Джонсона - Johnson's algorithm

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

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

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

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

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

Сначала к графу добавляется новый узел $q$ , связанный ребрами с нулевым весом с каждым из других узлов.
Во-вторых, алгоритм Беллмана – Форда используется, начиная с новой вершины $q$ , для нахождения для каждой вершины $v$ минимального веса $h (v)$ пути из $q$ в $v$ . Если на этом этапе обнаруживается отрицательный цикл, алгоритм завершается.
Затем ребра исходного графа повторно взвешиваются с использованием значений, вычисленных алгоритмом Беллмана – Форда: ребро от $u$ до $v$ , имеющее длину , получает новую длину $w$ $($ $u$ $,$ $v$ $) +$ $h$ $($ $u$ $) -$ $h$ $($ $v$ $)$ . ${\ Displaystyle ш (и, v)}$
Наконец, $q$ удаляется, и алгоритм Дейкстры используется для поиска кратчайших путей от каждого узла $s$ к каждой другой вершине в пересмотренном графе. Расстояние в исходном графе затем вычисляется для каждого расстояния $D$ ( $u$ , $v$ ) путем добавления $h (v) - h (u)$ к расстоянию, возвращаемому алгоритмом Дейкстры.

Пример

Первые три этапа алгоритма Джонсона изображены на иллюстрации ниже.

График слева от иллюстрации имеет два отрицательных ребра, но не имеет отрицательных циклов. Центральный граф показывает новую вершину $q$ , дерево кратчайших путей, вычисленное алгоритмом Беллмана – Форда с $q в$ качестве начальной вершины, и значения $h (v),$ вычисленные в каждом другом узле, как длина кратчайшего пути от $q$ до этого узел. Обратите внимание, что все эти значения неположительны, потому что $q$ имеет ребро нулевой длины для каждой вершины, а кратчайший путь не может быть длиннее этого ребра. Справа показан взвешенный граф, образованный заменой веса каждого ребра на $w$ $($ $u$ $,$ $v$ $) +$ $h$ $($ $u$ $) -$ $h$ $($ $v$ $)$ . В этом пересмотренном графе все веса ребер неотрицательны, но для кратчайшего пути между любыми двумя узлами используется та же последовательность ребер, что и для кратчайшего пути между теми же двумя узлами в исходном графе. Алгоритм завершается применением алгоритма Дейкстры к каждому из четырех начальных узлов в взвешенном графе. ${\ Displaystyle ш (и, v)}$

Правильность

В пересмотренном графе ко всем путям между парой узлов $s$ и $t$ добавлено одинаковое количество $h (s) - h (t)$ . Предыдущее утверждение можно доказать следующим образом: пусть $p$ - путь. Его вес W в пересмотренном графе определяется следующим выражением: ${\ displaystyle st}$

{\ displaystyle {\ bigl (} w (s, p_ {1}) + h (s) -h (p_ {1}) {\ bigr)} + ​​{\ bigl (} w (p_ {1}, p_ { 2}) + h (p_ {1}) - h (p_ {2}) {\ bigr)} + ​​... + {\ bigl (} w (p_ {n}, t) + h (p_ {n} ) -h (t) {\ bigr)}.}

Каждый отменяется в предыдущем выражении в квадратных скобках; поэтому остается следующее выражение для W : ${\ Displaystyle + ч (п_ {я})}$ ${\ displaystyle -h (p_ {i})}$

{\ displaystyle {\ bigl (} вес (s, p_ {1}) + w (p_ {1}, p_ {2}) + ... + w (p_ {n}, t) {\ bigr)} + h (s) -h (t)}

Выражение в квадратных скобках - это вес p в исходном весе .

Поскольку повторное взвешивание добавляет одинаковую величину к весу каждого пути, путь является кратчайшим путем в исходном взвешивании тогда и только тогда, когда он является кратчайшим путем после повторного взвешивания. Вес ребер, принадлежащих кратчайшему пути от q к любому узлу, равен нулю, и поэтому длины кратчайших путей от q до каждого узла становятся равными нулю в перенастроенном графе; однако они по-прежнему остаются кратчайшими путями. Следовательно, не может быть отрицательных ребер: если ребро uv имело отрицательный вес после переназначения, то путь нулевой длины от q до u вместе с этим ребром образовал бы путь отрицательной длины от q до v , что противоречит тому факту, что все вершины находятся на нулевом расстоянии от q . Отсутствие отрицательных ребер обеспечивает оптимальность путей, найденных алгоритмом Дейкстры. Расстояния в исходном графе могут быть вычислены из расстояний, вычисленных алгоритмом Дейкстры в пересмотренном графе, путем обращения преобразования повторного взвешивания. ${\ displaystyle st}$

Анализ

Временная сложность этого алгоритма, используя кучи Фибоначчей в реализации алгоритма Дейкстров, является : алгоритм использует время для этапа Беллмана-Форд алгоритма, и для каждого из конкретизации алгоритма Дейкстры. Таким образом, когда граф разреженный , общее время может быть быстрее, чем алгоритм Флойда – Уоршалла , который решает ту же проблему во времени . ${\ Displaystyle O (| V | ^ {2} \ log | V | + | V || E |)}$ ${\ Displaystyle O (| V || E |)}$ ${\ Displaystyle O (| V | \ журнал | V | + | E |)}$ ${\ displaystyle | V |}$ ${\ Displaystyle O (| V | ^ {3})}$