, |V|=n,
соответствующий отношению R.
Тогда необходимо найти все пары вершин (x,y), соединенных некоторым путём.
Иными словами, требуется построить новое отношение R, которое будет состоять из всех пар (x,y) таких, что найдется последовательность x=x0,...,xk=y ∈ X, где (xi-1,xi) ∈ R, i=1..k.
Псевдокод
Изначально матрица W заполняется соответственно отношению R, то есть W[i][j] = [(i,j) ∈ R].
Затем внешним циклом перебираются все элементы k множества X и для каждого из них, если он может использоваться как промежуточный для соединения двух элементов i и j, отношение R расширяется добавлением в него пары (i,j).
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])
Доказательство
Рассмотрим произвольную пару вершин i,j Î V и все пути между ними, промежуточные вершины которых принадлежат множеству вершин с номерами {1,..,k}. Пусть p - некоторый из них. Докажем по индукции (по числу промежуточных вершин в пути), что после i-ой итерации внешнего цикла будет верно утверждение - если в построенном графе между выбранной парой вершин есть путь, содержащий в качестве промежуточных только вершины из множества вершин с номерами {v1,..,vi}, то между ними будет дуга.
База индукции. Если у нас нет промежуточных вершин, что соответствует начальной матрице смежности, то утверждение выполнено: либо есть дуга (путь не содержит промежуточных вершин), либо его нет.
Индуктивный переход. Пусть предположение выполнено для i = k - 1. Докажем, что оно верно и для i = k. Рассмотрим случаи (далее под вершиной будем понимать ее номер для простоты изложения):
k не является промежуточной вершиной пути p. Тогда все его промежуточные пути принадлежат множеству вершин с номерами {1,..,k-1}, то есть существует путь с промежуточными вершинами в исходном множестве. Это значит будет истиной. В противном случае будет ложью и на k-ом шаге ею и останется.
k является промежуточной вершиной предполагаемого пути p. Тогда этот путь можно разбить на два пути: . Пусть как , так и существуют. Тогда они содержат в качестве промежуточных вершины из множества (так как вершина - либо конечная, либо начальная, то она не может быть в множестве по нашему определению). Тогда и истинны и по индуктивному предположению посчитаны верно. Тогда и тоже истина. Пусть какого-то пути не существует. Тогда пути тоже не может существовать, так как добраться, например, от вершины до по вершинам из множества невозможно по индуктивному предположению. Тогда вся конъюнкция будет ложной, то есть такого пути нет, откуда после итерации будет ложью.
Таким образом, после завершения внешнего цикла у нас будет W[i][j] = true, если среди между этими вершинами есть путь, содержащий в качестве промежуточных вершины из множества всех остальные вершин графа, что и есть транзитивное замыкание.