Алгоритм Флойда — Уоршелла | |
---|---|
Предназначение | поиск в графе кратчайшего пути из одной вершины во все остальные |
Структура данных | граф |
Худшее время | |
Лучшее время | |
Среднее время | |
Затраты памяти |
Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. При этом алгоритм впервые разработал и опубликовал Бернард Рой (англ. Bernard Roy)[1] в 1959 году.
Пусть вершины графа пронумерованы от 1 до и введено обозначение для длины кратчайшего пути от до , который кроме самих вершин проходит только через вершины . Очевидно, что — длина (вес) ребра , если таковое существует (в противном случае его длина может быть обозначена как ).
Существует два варианта значения :
Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.
Тогда рекуррентная формула для имеет вид:
— длина ребра
Алгоритм Флойда-Уоршелла последовательно вычисляет все значения для от 1 до . Полученные значения являются длинами кратчайших путей между вершинами
На каждом шаге алгоритм генерирует матрицу Матрица содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица заполняется длинами рёбер графа (или запредельно большим M, если ребра нет).
for k = 1 to n for i = 1 to n for j = 1 to n W[i][j] = min(W[i][j], W[i][k] + W[k][j])
Три вложенных цикла содержат операцию, исполняемую за константное время. то есть алгоритм имеет кубическую сложность, при этом простым расширением можно получить также информацию о кратчайших путях — помимо расстояния между двумя узлами записывать в матрицу идентификатор первого узла в пути.
Алгоритм Флойда-Уоршелла может быть использован для нахождения замыкания отношения
по транзитивности. Для этого в качестве W[0]
используется бинарная матрица смежности графа,
; оператор min
заменяется дизъюнкцией, сложение заменяется конъюнкцией:
for k = 1 to n for i = 1 to n for j = 1 to n W[i][j] = W[i][j] or (W[i][k] and W[k][j])
После выполнения алгоритма матрица W
является матрицей достижимости.
Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до , где — длина битовой маски (в модели вычислений RAM). На практике, ещё бо́льшего ускорения можно достичь, используя такие специализированные наборы микропроцессорных команд, как SSE.
Алгоритм Флойда — Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет при применении двоичной кучи, что лучше, чем алгоритма Флойда — Уоршелла тогда, когда существенно меньше (условие плотности графа). Если граф разрежен, у него имеются рёбра с отрицательным весом и отсутствуют циклы с отрицательным суммарным весом, то используется алгоритм Джонсона, который имеет ту же сложность, что и вариант с алгоритмом Дейкстры.
Также являются известными алгоритмы с применением алгоритмов быстрого перемножения матриц, которые ускоряют вычисления в плотных графах, но они обычно имеют дополнительные ограничения (например, представление весов рёбер в виде малых целых чисел)[2][3]. Вместе с тем, из-за большого константного фактора времени выполнения преимущество при вычислениях над алгоритмом Флойда — Уоршелла проявляется только на больших графах.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .