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

Метод поиска пути на основе компьютера

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

Анализ

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

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

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