Алгоритм Флойда — Уоршалла — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Алгоритм == Пусть вершины графа <tex>G=(V,\; E),\; |V| = n</tex> пронумерованы от 1 до <tex>n</tex> и введено ...»)
 
Строка 1: Строка 1:
 +
==Задача==
 +
Пусть дано отношение <tex>R</tex> на множестве <tex>X</tex>. Необходимо построить его [[Транзитивное замыкание|транзитивное замыкание]] <tex>\mathrm{TrCl}(R)</tex>.
 
== Алгоритм ==
 
== Алгоритм ==
 +
Пусть вершины графа <tex>G=(V,\; E),\; |V| = n</tex> пронумерованы от 1 до <tex>n</tex>. Каждая вершина соответствует элементу множества. А наличие ребра между вершинами означает, что соответствующие элементы множества состоят в отношении. Пусть так же введено булево обозначение <tex>d_{i j}^{k}</tex> для наличия пути (равно true, если есть путь, и false {{---}} в противном случае) от <tex>i</tex> до <tex>j</tex>, который кроме самих вершин <tex>i,\; j</tex> проходит только через вершины <tex>1 \ldots k</tex>(с номерами <tex> \le k </tex>).
  
Пусть вершины графа <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>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} \cap d_{k j}^{k-1}</tex>
  
Существует два варианта значения <tex>d_{i j}^{k},\;k \in \mathbb (1,\;\ldots,\;n)</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>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> заполняется длинами рёбер графа.
+
На каждом шаге алгоритм генерирует двумерную матрицу <tex>W</tex>, <tex>w_{ij}=d_{i j}^n</tex>. Матрица <tex>W</tex> содержит транзитивное замыкание графа. Перед работой алгоритма матрица <tex>W</tex> заполняется true или false в зависимости от наличия ребра в графе.
  
 
  for k = 1 to n
 
  for k = 1 to n
 
   for i = 1 to n
 
   for i = 1 to n
 
     for j = 1 to n
 
     for j = 1 to n
       W[i][j] = min(W[i][j], W[i][k] + W[k][j])
+
       W[i][j] = W[i][k] and W[k][j]
  
 
=== Сложность алгоритма ===
 
=== Сложность алгоритма ===
Строка 31: Строка 21:
 
<tex>\sum_{n,\;n,\;n}O(1) = O(n^3),</tex>
 
<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).
 
  
 
== Ссылки ==
 
== Ссылки ==

Версия 02:16, 15 ноября 2011

Задача

Пусть дано отношение [math]R[/math] на множестве [math]X[/math]. Необходимо построить его транзитивное замыкание [math]\mathrm{TrCl}(R)[/math].

Алгоритм

Пусть вершины графа [math]G=(V,\; E),\; |V| = n[/math] пронумерованы от 1 до [math]n[/math]. Каждая вершина соответствует элементу множества. А наличие ребра между вершинами означает, что соответствующие элементы множества состоят в отношении. Пусть так же введено булево обозначение [math]d_{i j}^{k}[/math] для наличия пути (равно true, если есть путь, и false — в противном случае) от [math]i[/math] до [math]j[/math], который кроме самих вершин [math]i,\; j[/math] проходит только через вершины [math]1 \ldots k[/math](с номерами [math] \le k [/math]).

Тогда существующий путь между [math]i,\;j[/math], проходящий через [math]k[/math] (сначала он идет от [math]i[/math] до [math]k[/math], а потом от [math]k[/math] до [math]j[/math]), очевидно, выражается, как [math]d_{i j}^{k}=d_{i k}^{k-1} \cap d_{k j}^{k-1}[/math]

Алгоритм Флойда — Уоршелла последовательно вычисляет все значения [math]d_{i j}^{k}[/math], [math]\forall i,\; j[/math] для [math]k[/math] от 1 до [math]n[/math]. Полученные значения [math]d_{i j}^{n}[/math] являются транзитивным замыканием графа.

Псевдокод

На каждом шаге алгоритм генерирует двумерную матрицу [math]W[/math], [math]w_{ij}=d_{i j}^n[/math]. Матрица [math]W[/math] содержит транзитивное замыкание графа. Перед работой алгоритма матрица [math]W[/math] заполняется true или false в зависимости от наличия ребра в графе.

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      W[i][j] = W[i][k] and W[k][j]

Сложность алгоритма

Три вложенных цикла содержат операцию, исполняемую за константное время. [math]\sum_{n,\;n,\;n}O(1) = O(n^3),[/math] то есть алгоритм имеет кубическую сложность, при этом простым расширением можно получить также информацию о кратчайших путях — помимо расстояния между двумя узлами записывать матрицу идентификатор первого узла в пути.

Ссылки