Изменения
→Алгоритм
== Алгоритм ==
Сформулируем нашу задачу в терминах графов: рассмотрим граф <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 in R, i = 1, 2, \dots, k </tex>.
=== Псевдокод ===
=== Обоснование ===
<wikitex>
Покажем, что если в отношении $R$ существовал путь $x = x_0, x_1, \dots, x_k = y$, то после работы алгоритма отношение $T$ будет содержать пару $(x, y)$. Действительно, как только параметр внешнего цикла дойдет до вершины $u$, лежащей внутри этого пути, то обязательно появится дуга, минующая эту вершину, то есть появится путь из $x$ в $y$ на одну дугу короче предыдущего. После полного просмотра элементов множества $MX$ внешним циклом мы исключим все промежуточные вершины.</wikitex>
=== Сложность алгоритма ===
Три вложенных цикла работают за время <tex>\sum\limits_{n}\sum\limits_{n}\sum\limits_{n}O(1) = O(n^3)</tex>,
