- Алгоритм Джонсона
-
Алгоритмы поиска на графах - A*
- B*
- Алгоритм Беллмана — Форда
- Двунаправленный поиск
- Алгоритм Дейкстры
- Алгоритм Джонсона
- Поиск в ширину
- Поиск в глубину
- Поиск с ограничением глубины
- Поиск по первому наилучшему совпадению
- Алгоритм Флойда — Уоршелла
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.
Содержание
Алгоритм
Дан граф с весовой функцией . Если веса всех рёбер в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся рёбра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество рёбер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов рёбер , должно удовлетворять следующим свойствам.
- Для всех рёбер новый вес .
- Для всех пар вершин путь является кратчайшим путем из вершины в вершину с использованием весовой функции тогда и только тогда, когда — также кратчайший путь из вершины в вершину с весовой функцией .
Сохранение кратчайших путей
Лемма (Изменение весов сохраняет кратчайшие пути). Пусть дан взвешенный ориентированный граф с весовой функцией , и пусть — произвольная функция, отображающая вершины на действительные числа. Для каждого ребра определим
Пусть — произвольный путь из вершины в вершину . является кратчайшим путем с весовой функцией тогда и только тогда, когда он является кратчайшим путем с весовой функцией , то есть равенство равносильно равенству . Кроме того, граф содержит цикл с отрицательным весом с использованием весовой функции тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции .
Изменение веса
- Для данного графа создадим новый граф , где , для некоторой новой вершины , а .
- Расширим весовую функцию таким образом, чтобы для всех вершин выполнялось равенство .
- Далее определим для всех вершин величину и новые веса для всех рёбер .
Основная процедура
В алгоритме Джонсона используется алгоритм Беллмана — Форда и алгоритм Дейкстры, реализованные в виде подпрограмм. Рёбра хранятся в виде списков смежных вершин. Алгоритм возврашает обычную матрицу размером , где , или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.
Алгоритм Джонсона
Строится граф if Bellman_Ford = FALSE then print «Входной граф содержит цикл с отрицательным весом» else for для каждой do присвоить величине значение , вычисленное алгоритмом Беллмана — Форда for для каждого ребра do for для каждой вершины do вычисление с помощью алгоритма Дейкстры величин для всех вершин for для каждой вершины do return D
Сложность
Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно . При более простой реализации неубывающей очереди с приоритетами время работы становится равным , но для разреженных графов эта величина в асимптотическом пределе ведёт себя лучше, чем время работы алгоритма Флойда — Уоршелла.
См. также
Ссылки
Литература
- Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4
Категории:- Алгоритмы поиска
- Алгоритмы на графах
Wikimedia Foundation. 2010.