Редактирование: Алгоритм Флойда — Уоршалла

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
#перенаправление [[Алгоритм Флойда]]
+
== Алгоритм ==
 +
 
 +
Пусть вершины графа <tex>G=(V,\; E),\; |V| = n</tex> пронумерованы от 1 до <tex>n</tex> и введено обозначение <tex>d_{i j}^{k}</tex> для длины кратчайшего пути от <tex>i</tex> до <tex>j</tex>, который кроме самих вершин <tex>i,\; j</tex> проходит только через вершины <tex>1 \ldots k</tex>(с номерами <tex> \le k </tex>). Очевидно, что <tex>d_{i j}^{0}</tex> — длина (вес) ребра <tex>(i,\;j)</tex>, если таковое существует (в противном случае его длина может быть обозначена как <tex>\infty</tex>)
 +
 
 +
Существует два варианта значения <tex>d_{i j}^{k},\;k \in \mathbb (1,\;\ldots,\;n)</tex>:
 +
 
 +
# Кратчайший путь между <tex>i,\;j</tex> не проходит через вершину <tex>k</tex>, тогда <tex>d_{i j}^{k}=d_{i j}^{k-1}</tex>
 +
# Существует более короткий путь между <tex>i,\;j</tex>, проходящий через <tex>k</tex>, тогда он сначала идёт от <tex>i</tex> до <tex>k</tex>, а потом от <tex>k</tex> до <tex>j</tex>. В этом случае, очевидно, <tex>d_{i j}^{k}=d_{i k}^{k-1} + d_{k j}^{k-1}</tex>
 +
 
 +
Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.
 +
 
 +
Тогда рекуррентная формула для <tex>d_{i j}^k</tex> имеет вид:
 +
 
 +
<tex>d_{i j}^0</tex> — длина ребра <tex>(i,\;j)</tex>
 +
 
 +
<tex>d_{i j}^{k} = \min (d_{i j}^{k-1},\; d_{i k}^{k-1} + d_{k j}^{k-1})</tex>
 +
 
 +
Алгоритм Флойда — Уоршелла последовательно вычисляет все значения <tex>d_{i j}^{k}</tex>, <tex>\forall i,\; j</tex> для <tex>k</tex> от 1 до <tex>n</tex>. Полученные значения <tex>d_{i j}^{n}</tex> являются длинами кратчайших путей между вершинами <tex>i,\; j</tex>.
 +
 
 +
=== Псевдокод ===
 +
 
 +
На каждом шаге алгоритм генерирует двумерную матрицу <tex>W</tex>, <tex>w_{ij}=d_{i j}^n</tex>. Матрица <tex>W</tex> содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица <tex>W</tex> заполняется длинами рёбер графа.
 +
 
 +
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])
 +
 
 +
=== Сложность алгоритма ===
 +
Три вложенных цикла содержат операцию, исполняемую за константное время.
 +
<tex>\sum_{n,\;n,\;n}O(1) = O(n^3),</tex>
 +
то есть алгоритм имеет кубическую сложность, при этом простым расширением можно получить также информацию о кратчайших путях — помимо расстояния между двумя узлами записывать матрицу идентификатор первого узла в пути.
 +
 
 +
== Применение вариаций алгоритма ==
 +
 
 +
=== Построение матрицы достижимости ===
 +
 
 +
Алгоритм Флойда — Уоршелла может быть использован для нахождения замыкания отношения <tex>E</tex> по транзитивности. Для этого в качестве <code>W[0]</code> используется бинарная матрица смежности графа, <tex>({w^0}_{i j})_{n \times n} = 1 \Leftrightarrow (i,\; j) \in E</tex>; оператор <code>min</code> заменяется дизъюнкцией, сложение заменяется конъюнкцией:
 +
 
 +
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])
 +
 
 +
 
 +
После выполнения алгоритма матрица <code>W</code> является матрицей достижимости.
 +
 
 +
Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до <tex>O(n^3 / k)</tex>, где <tex>k</tex> - длина битовой маски (в модели вычислений RAM).
 +
 
 +
== Ссылки ==
 +
* [http://e-maxx.ru/algo/floyd_warshall_algorithm Реализация алгоритма Флойда на С++]
 +
* [http://plagiata.net.ru/?p=57 Реализация алгоритма Флойда на Delphi]
 +
* [http://rain.ifmo.ru/cat/data/vis/graph-paths/floyd-warshall-2004/code.jar Визуализатор]
 +
* [http://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедия]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)