Рубрики

Алгоритм Джонсона для всех пар кратчайших путей

Проблема состоит в том, чтобы найти кратчайшие пути между каждой парой вершин в данном взвешенном ориентированном графе, и веса могут быть отрицательными. Мы обсудили алгоритм Флойда Варшалла для этой проблемы. Временная сложность алгоритма Флойда Варшалла равна Θ (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 нет ребра. Все ребра из с.

3) Пересчитать края исходного графа. Для каждого ребра (u, v) присвойте новый вес как «исходный вес + h [u] — h [v]».

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

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

 ч [v]

Свойство просто означает, что кратчайшее расстояние от 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 [] = {0, -5, -1, 0}. Как только мы получим эти расстояния, мы удалим исходную вершину 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 ). Но для разреженных графов алгоритм работает намного лучше, чем Флойд Варшелл .

Ссылки:
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест
http://www.youtube.com/watch?v=b6LOHvCzmkI
http://www.youtube.com/watch?v=TV2Z6nbo1ic
http://en.wikipedia.org/wiki/Johnson%27s_algorithm
http://www.youtube.com/watch?v=Sygq1e0xWnM

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

Рекомендуемые посты:

Алгоритм Джонсона для всех пар кратчайших путей

0.00 (0%) 0 votes