Алгоритм Джонсона - Johnsons algorithm - Wikipedia

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

Учебный класс	Задача о кратчайшем пути для всех пар (для взвешенных графиков)
Структура данных	График
Худший случай спектакль	${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$

Для одноименного алгоритма планирования см. Планирование работы магазина.

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

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

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

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

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

Пример

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

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

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

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

${\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 )}.}$

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

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

Выражение в квадратных скобках означает вес п в исходном весе.

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

Анализ

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

Рекомендации

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

внешняя ссылка

• Boost: Кратчайшие пути для всех пар