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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
==Задача==
 
==Задача==
−
Пусть дано отношение <tex>R</tex> на множестве <tex>X</tex>. Необходимо построить его [[Транзитивное замыкание|транзитивное замыкание]] <tex>\mathrm{TrCl}(R)</tex>.
+
Пусть дано отношение <tex>R</tex> на множестве <tex>X</tex>. Необходимо построить его [[Транзитивное замыкание|транзитивное замыкание]] <tex>T = \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>, соответствующий отношению <tex>R</tex>. Тогда необходимо найти все пары вершин <tex>(x, y) </tex>, соединенных некоторым путем.
−
 
+
Иными словами, требуется построить новое отношение <tex>T</tex>, которое будет состоять из всех пар <tex>(x, y) </tex> таких, что найдется последовательность <tex>x = x_0, x_1, \dots, x_k = y </tex>, где <tex> (x_{i-1}, x_i) \subset R, i = 1, 2, \dots, k </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}</tex>, <tex>\forall i,\; j</tex> для <tex>k</tex> от 1 до <tex>n</tex>. Полученные значения <tex>d_{i j}^{n}</tex> являются транзитивным замыканием графа.
 
  
 
=== Псевдокод ===
 
=== Псевдокод ===
−
 
+
Изначально матрица <tex>W</tex> заполняется соответственно отношению <tex>R</tex>, то есть <tex>W[i][j] = ((i, ) \subset R) </tex>. Затем внешним циклом перебираются все элементы множества <tex>X</tex> и для каждого <tex>k</tex> из них, если он может использоваться, как промежуточный для соединения двух элементов <tex>i</tex> и <tex>j</tex>, отношение <tex>T</tex> расширяется добавлением в него пары <tex>(i, j)</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
Строка 17: Строка 14:
 
       W[i][j] = W[i][j] or (W[i][k] and W[k][j])
 
       W[i][j] = W[i][j] or (W[i][k] and W[k][j])
  
 +
=== Обоснование ===
 +
<wikitex>
 +
Покажем, что если в отношении $R$ существовал путь $x = x_0, x_1, \dots, x_k = y$, то после работы алгоритма отношение $T$ будет содержать пару $(x, y)$. Действительно, как только параметр внешнего цикла дойдет до вершины $u$, лежащей внутри этого пути, то обязательно появится дуга, минующая эту вершину, то есть появится путь из $x$ в $y$ на одну дугу короче предыдущего. После полного просмотра элементов множества $M$ внешним циклом мы исключим все промежуточные вершины.</wikitex>
 
=== Сложность алгоритма ===
 
=== Сложность алгоритма ===
 
Три вложенных цикла работают за время <tex>\sum\limits_{n}\sum\limits_{n}\sum\limits_{n}O(1) = O(n^3)</tex>,  
 
Три вложенных цикла работают за время <tex>\sum\limits_{n}\sum\limits_{n}\sum\limits_{n}O(1) = O(n^3)</tex>,  

Версия 02:40, 24 ноября 2011

Задача

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

Алгоритм

Сформулируем нашу задачу в терминах графов: рассмотрим граф [math]G=(V,\; E),\; |V| = n[/math], соответствующий отношению [math]R[/math]. Тогда необходимо найти все пары вершин [math](x, y) [/math], соединенных некоторым путем. Иными словами, требуется построить новое отношение [math]T[/math], которое будет состоять из всех пар [math](x, y) [/math] таких, что найдется последовательность [math]x = x_0, x_1, \dots, x_k = y [/math], где [math] (x_{i-1}, x_i) \subset R, i = 1, 2, \dots, k [/math].

Псевдокод

Изначально матрица [math]W[/math] заполняется соответственно отношению [math]R[/math], то есть [math]W[i][j] = ((i, ) \subset R) [/math]. Затем внешним циклом перебираются все элементы множества [math]X[/math] и для каждого [math]k[/math] из них, если он может использоваться, как промежуточный для соединения двух элементов [math]i[/math] и [math]j[/math], отношение [math]T[/math] расширяется добавлением в него пары [math](i, j)[/math]. 

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])

Обоснование

<wikitex> Покажем, что если в отношении $R$ существовал путь $x = x_0, x_1, \dots, x_k = y$, то после работы алгоритма отношение $T$ будет содержать пару $(x, y)$. Действительно, как только параметр внешнего цикла дойдет до вершины $u$, лежащей внутри этого пути, то обязательно появится дуга, минующая эту вершину, то есть появится путь из $x$ в $y$ на одну дугу короче предыдущего. После полного просмотра элементов множества $M$ внешним циклом мы исключим все промежуточные вершины.</wikitex>

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

Три вложенных цикла работают за время [math]\sum\limits_{n}\sum\limits_{n}\sum\limits_{n}O(1) = O(n^3)[/math], то есть алгоритм имеет кубическую сложность.

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Флойда_—_Уоршалла&oldid=13416»