==Задача==
Пусть дано отношение <tex>R</tex> на множестве <tex>X</tex>. Необходимо построить его [[Транзитивное замыкание|транзитивное замыкание]] <tex>T = \mathrm{TrCl}(R)</tex>.
== Алгоритм ==
Пусть вершины графа Сформулируем нашу задачу в терминах графов: рассмотрим граф <tex>G=(V,\; E),\; |V| = n</tex> пронумерованы от 1 до , соответствующий отношению <tex>nR</tex>. Каждая вершина соответствует элементу множества. А наличие ребра между вершинами означает, что соответствующие элементы множества состоят в отношении. Пусть так же введено булева величина Тогда необходимо найти все пары вершин <tex>d_{i j}^{k}</tex> для наличия пути (равно true, если есть путьx, и false {{---}} в противном случаеy) от <tex>i</tex> до <tex>j</tex>, который кроме самих вершин <tex>i,\; j</tex> проходит только через вершины <tex>1 \ldots k</tex>(с номерами <tex> \le k </tex>)соединенных некоторым путем. Тогда существующий путь между Иными словами, требуется построить новое отношение <tex>i,\;jT</tex>, проходящий через <tex>kкоторое будет состоять из всех пар </tex> (сначала он идет от <tex>i</tex> до <tex>kx, y) </tex>таких, а потом от что найдется последовательность <tex>k</tex> до <tex>j</tex>)x = x_0, очевидноx_1, выражается\dots, как <tex>d_{i j}^{k}x_k =d_{i k}^{k-1} \cap d_{k j}^{k-1}y </tex> Алгоритм Флойда — Уоршелла последовательно вычисляет все значения , где <tex>d_(x_{i j-1}^{k}</tex>, <tex>x_i) \forall subset R, i= 1, 2,\; j</tex> для <tex>dots, k</tex> от 1 до <tex>n</tex>. Полученные значения <tex>d_{i j}^{n}</tex> являются транзитивным замыканием графа.
=== Псевдокод ===
На каждом шаге алгоритм генерирует двумерную матрицу Изначально матрица <tex>W</tex> заполняется соответственно отношению <tex>R</tex>, то есть <tex>w_{ij}W[i][j] =d_{((i j}^n, ) \subset R) </tex>. Матрица Затем внешним циклом перебираются все элементы множества <tex>X</tex> и для каждого <tex>k</tex> из них, если он может использоваться, как промежуточный для соединения двух элементов <tex>i</tex> и <tex>Wj</tex> содержит транзитивное замыкание графа. Перед работой алгоритма матрица , отношение <tex>WT</tex> заполняется true или false расширяется добавлением в зависимости от наличия ребра в графенего пары <tex>(i, j)</tex>.
for k = 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>
=== Сложность алгоритма ===
Три вложенных цикла работают за время <tex>\sum\limits_{n}\sum\limits_{n}\sum\limits_{n}O(1) = O(n^3)</tex>,
