Алгоритм Джонсона

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

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

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

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

Алгоритм Джонсона состоит из следующих шагов: ^{[ 1 ]}^{[ 2 ]}

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

Пример

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

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

Корректность

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

$\left(w(s,p_{1})+h(s)-h(p_{1})\right)+\left(w(p_{1},p_{2})+h(p_{1})-h(p_{2})\right)+...+\left(w(p_{n},t)+h(p_{n})-h(t)\right).$

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

$\left(w(s,p_{1})+w(p_{1},p_{2})+\cdots +w(p_{n},t)\right)+h(s)-h(t)$

Выражение в квадратных скобках представляет собой вес p в исходном весе.

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

Анализ

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

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), Введение в алгоритмы , MIT Press и McGraw-Hill, ISBN 978-0-262-03293-3 . Раздел 25.3, «Алгоритм Джонсона для разреженных графов», стр. 636–640.
^ Перейти обратно: ^а ^б Блэк, Пол Э. (2004), «Алгоритм Джонсона», Словарь алгоритмов и структур данных , Национальный институт стандартов и технологий .
^ Джонсон, Дональд Б. (1977), «Эффективные алгоритмы поиска кратчайших путей в разреженных сетях», Журнал ACM , 24 (1): 1–13, doi : 10.1145/321992.321993 , S2CID 207678246 .
^ Суурбалле, JW (1974), «Непересекающиеся пути в сети», Networks , 14 (2): 125–145, doi : 10.1002/net.3230040204 .

Внешние ссылки

Повышение: кратчайшие пути для всех пар

[clrs-1] Перейти обратно: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), Введение в алгоритмы , MIT Press и McGraw-Hill, ISBN 978-0-262-03293-3 . Раздел 25.3, «Алгоритм Джонсона для разреженных графов», стр. 636–640.

[black-2] Перейти обратно: ^а ^б Блэк, Пол Э. (2004), «Алгоритм Джонсона», Словарь алгоритмов и структур данных , Национальный институт стандартов и технологий .

[3] Джонсон, Дональд Б. (1977), «Эффективные алгоритмы поиска кратчайших путей в разреженных сетях», Журнал ACM , 24 (1): 1–13, doi : 10.1145/321992.321993 , S2CID 207678246 .

[4] Суурбалле, JW (1974), «Непересекающиеся пути в сети», Networks , 14 (2): 125–145, doi : 10.1002/net.3230040204 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

v т и графов и деревьев Алгоритмы обхода
Поиск	обрезка a–b А* ИДА* МПА* СМА* Поиск по принципу «лучшее в первую очередь» Поиск луча Двунаправленный поиск Поиск в ширину Лексикографический Параллельно Б* Поиск в глубину Итеративное углубление Д* Граничный поиск Поиск точки прыжка Поиск по дереву Монте-Карло ССС*
Кратчайший путь	Беллман-Форд Дейкстры Флойд-Уоршалл Джонсонс Кратчайший путь быстрее Йен
Минимальное связующее дерево	Черника Крускала Прим Обратное удаление
Список алгоритмов поиска по графу