Будем рассматривать ориентированные графы G = <V, E>, дугам которых приписаны веса. Это означает, что каждой дуге <u, v> ОE поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

Полагаем, кроме того, a (u, v) = ╔ , если u -a v.

Если последовательность вершин v₀, v₁,..., v_p определяет путь в G, то его длина определяется как сумма
 
 

(Отметим, что если в произвольном графе мы примем вес каждой дуги равным единице, то мы получим обычное определение длины пути как числа дуг; длина пути равна 0 при p = 0).

Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, t ОV. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = ╔ . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v₁,..., v_p не будет повторов.

С другой стороны, если в графе существует контур отрицательной длины, то расстояние между некоторыми парами вершин становится неопределенным, потому что, обходя этот контур достаточное число раз, мы можем показать путь между этими вершинами с длиной, меньшей произвольного вещественного числа. В таком случае, можно было бы говорить о длине кратчайшего элементарного пути, однако задача, поставленная таким образом, вероятно будет значительно более сложной, так как, в частности, она содержит в себе задачу существования гамильтонова пути.

Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем затем кратчайшие пути между городами. Вес дуги также может соответствовать стоимости (или времени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну ситуацию получаем, когда вес дуги <u, v> равен вероятности p(u, v) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляющих его дуг. Задачу нахождения наиболее надежного пути легко можно свести к задаче о кратчайшем пути, заменяя веса p(u, v) на a (u, v) = - log p(u, v).

Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этого достаточно отметить, что для произвольных s, t О V (s ╧ t) существует вершина v, такая что
 
 

Действительно, таким свойством обладает предпоследняя вершина произвольного кратчайшего пути из s в t.

Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a (u, v), и т.д.

Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u, ... не сожержит повторений и оканчивается вершиной s.

Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.

Таким образом, мы получаем следующий алгоритм:
 
 

Данные: Расстояния D[v] от фиксированной вершины s до всех остальных вершин v О V, фиксированная вершина t, матрица весов ребер, A[u, v], u, v ОV.

Результаты: СТЕК содержит последовательность вершин, определяющую кратчайший путь из s в t.

begin

CTEK := Ж ; CTEK Ь t; v:= t;

while v ╧ s do

begin

u := вершина, для которой D[v] = D[u] + A[u, v];

CTEK Ь u;

v:= u

end

end.
 
 

Пусть <V, E> -ориентированный граф, | V|  = n, | E|  = m. Если выбор вершины u происходит в результате просмотра всех вершин, то сложность нашего алгоритма - O(n²). Если мы просматриваем только список ПРЕДШ[v], содержащий все вершины u, такие что u (r) v, то в этом случае сложность будет O(m).

Отметим, что в случае положительных весов ребер задача о кратчайшем пути в неориентированном графе легко сводится к аналогичной задаче для некоторого ориентированного графа. С этой целью достаточно заменить каждое ребро {u, v}двумя дугами б u, vси бv, uс , каждая с таким же весом, что и {u, v}. Однако в случае неположительных весов это приводит к возникновению контуров с неположительной длиной.

Далее будем всегда предполагать, что G = < V, E>является ориентированным графом, |V|  = n, |E|  = m. В целях упрощения изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых ╚ большинство╩ вершин изолированные.

Будем также предполагать, что веса дуг запоминаются в массиве A[u, v], u, vО V (A[u, v] содержит вес a (u, v)).
 
 

Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A[u, v], u, v О V, вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин v О V. Каждый раз, когда мы устанавливаем, что
 
 

оценку D[v] улучшаем: D[v] = D[u] + A[u, v].

Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно.

Легко можно показать, что значение каждой из переменных D[v] равно тогда d (s, v) - расстоянию от s до v.

Заметим, что для того чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа.

Не известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных.

Описанная общая схема является неполной, так как она не определяет очередности, в которой выбираются вершины u и v для проверки условия минимальности расстояния. Эта очередности, как будет показано ниже, очень сильно влияет на эффективность алгоритма. Опишем теперь более детально методы нахождения расстояния от фиксированной вершины, называемой источником, его всегда будем обозначать через s, до всех остальных вершин графа.

Сначала представим алгоритм для общего случая, в котором предполагается только отсутствие контуров с отрицательной длиной. С эти алгоритмом обычно связывают имена Л.Р. Форда и Р.Е. Беллмана.
 
 

Данные: Ориентированный граф <V, E> с n вершинами с выделенным источником s О V, матрица дуг A[u, v], u, v ОV (граф не содержит контуров отрицательной длины).

Результаты: Расстояния от источника до всех вершин графа: D[v]=d(s, v), vО V.

1 begin

2 for v О V do D [v] := A[s, v]; D [s]:= 0;

3 for k  := 1 to n - 2 do

4 for v О V \ {s} do

5 for u О V do D [v] := min(D[v], D[u] + A [u, v])

6 end
 
 

Докажем правильность этого алгоритма. Для этого обозначим через d^(m)(v) длину кратчайшего из путей из s в v, содержащих не более m дуг (d^(m)(v) = ╔ , если не существует ни одного такого пути). Тогда имеем

Покажем теперь, что если при входе в очередную итерацию цикла 3

что, принимая во внимание равенство (1) дает условие (3).

Отметим, что при входе в цикл 3 имеем D[v] = d 1 (v), v О V, следовательно, после выполнения n - 2 итераций этого цикла будут выполняться неравенства d (s, v) ё D[v] ёd^(n-1)(v), v О V.

Теперь достаточно показать, что d^(n-1)(v) = d (s, v). Это справедливо, поскольку каждый путь более чем с n - 1 дугами содержит контур, устранение которого не увеличивает длины пути (ведь мы предполагаем отсутствие контуров отрицательной длины). Тем самым закончено доказательство корректности алгоритма.

Очевидно, что временная сложность алгоритма есть O(n³). Мы можем, конечно, закончить вычисления, когда выполнение цикла 4 не вызывает изменения ни одной из переменных D[v], v О V. Это может наступить для k < n - 2, однако такая модификация алгоритма не изменяет существенным образом его сложности. Для редких графов (m << n²) удобнее представлять граф списками инцидентности ПРЕДШ[v], v О V. Заменяя строку 5 на

for u О ПРЕДШ[v] do D [v] :=min(D[v], D[u] + A [u, v]),

получаем алгоритм со сложностью O(nm).

Работа алгоритма Форда - Беллмана проиллюстрирована на следующем рисунке (V = {1, ..., 5}, веса дуг даны числами в скобках, циклы 4 и 5 выполняются в порядке возрастания номеров вершин).
 
 

 
 
 
 
 
 
 
 

k	D[1]	D[2]	D[3]	D[4]	D[5]
	0	1	╔	╔	3
1	0	1	4	4	-1
2	0	1	4	3	-1
3	0	1	4	3	-1

 

Известны более эффективные алгоритмы для двух важных случаев, а именно: когда веса всех дуг неотрицательны или когда граф бесконтурный. Сначала опишем алгоритм для первого случая - алгоритм Дейкстры.
 
 

Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг - метод Дейкстры

Данные: Ориентированный граф бV, Eс с выделенным источником s О V, матрица весов дуг A [u, v], u, v О V (все веса неотрицательны).

Результаты: Расстояния от источника до всех вершин графа D[v] = d(s, v), vО V.

1 begin

2 for v О V do D [v] := A[s, v]; D [s]:= 0;

3 T := V \ {s};

4 while T ╧ Жdo

5 begin

6 u := произвольная вершина r О T, такая что D[r] = min(D[p]: p О T};

7 T := T \ {u};

8 for v О T do D [v] := min(D[v], D[u] + A [u, v])

9 end

10 end
 
 

Чтобы понять действие алгоритма, покажем, что следующее условие является инвариантом цикла 4: для каждой v О V \ T D[v] = d(s, v),

для каждой v ОT D[v] = длине кратчайшего из тех путей из s в v, для которых предпоследняя вершина принадлежит множеству V \ T. (4)

В самом деле, в строке 6 мы находим вершину u О T, такую что значение D[u]  является минимальным (из всех) значением D[t], для t О T.

Покажем, что D[u] = d(s, u). Это именно так, потому что если кратчайший путь из s в u имеет длину меньше D[u], то в силу второй части условия (4) его предпоследняя вершина принадлежит множеству T.

Пусть t будет первой вершиной пути, принадлежащей множеству T. Начальный отрезок пути из s в t составляет кратчайший путь из s в t, причем его предпоследняя вершина не принадлежит множеству T. По второй части условия (4) имеем D[t] = d(s, t). Используя предположение о неотрицательности весов, получаем
 
 

вопреки принципу, по которому была выбрана вершина u.

Таким образом, D[u] = d(s, u) и мы можем в строке 7 удалить u из множества T , не нарушая первой части условия (4). Чтобы обеспечить выполнение также и второй части этого условия, следует еще проверить пути из из s в v О T, предпоследняя вершина в которых есть u, и выполнить актуализацию переменных D [v], v О T. Именно это выполняет цикл 8.

Очевидно, что условие (4) выполняется при входе в цикл 4. По окончании действия алгоритма T = Ж , а следовательно, согласно условию (4), D[v] = d(s, v), v О V.

Оценим сложность алгоритма Дейкстры. Цикл 4 выполняется n - 1 раз, причем каждое его выполнение требует O(n) шагов: O(n) шагов для нахождения вершины u в строке 6 (предполагаем, что множество T представлено списком) и O(n) шагов для выполнения цикла 8. Таким образом, сложность алгоритма есть O(n²).

Тщательно подбирая структуры данных, можно получить вариант алгоритма со сложностью O(m log n). Для этого множество T нужно представить бинарным деревом с высотой O(log n) и с таким свойством, что для произвольных его вершин u и v :

если u - сын v, то D[u] ё D[v]
 
 

Вершина u, для которой значение D[u]  минимально, является тогда корнем дерева. Этот корень можно устранить за O(log n) шагов, сохраняя свойство уменьшения значения D[j] на каждом пути до корня. Достаточно сместить на место корня его сына s с большим (или равным) значением D[j], затем на освободившееся место передвинуть сына вершины s с большим значением D[j] и т.д. Если граф представлен списками ЗАПИСЬ[u], u О V, то строку 8 можно заменить на

for v О ЗАПИСЬ [u] do

if D[u] + A [u, v] < D[v] then

begin

D[v] :=  D[u] + A [u, v];

передвинуть вершину в дереве в направлении корня так, чтобы сохранить

условие если u - сын v, то D[u] ё D[v]

end
 
 

Если предположить существование таблицы указателей на вершины нашего дерева, то передвижение вершины v, о которой идет речь в данной части раздела, может быть осуществлено за O(log n) шагов. Достаточно заменять v поочередно вершинами, находящимися непосредственно над ней.

В алгоритме, модифицированном таким способом, каждая дуга графа анализируется в точности один раз, причем с этим связано O(log n) шагов на передвижение соответствующей вершины в дереве, представляющем множество T. Это дает в сумме O(m log n) шагов. Сюда нужно добавить O(n log n) шагов, необходимых для построения нашего дерева и для устранения n - 1 раз из него корня. Общая сложность алгоритма есть O(m log n).

Неизвестно, существует ли алгоритм сложности O(m) нахождения расстояния от фиксированной вершины до всех остальных вершин графа с неотрицательными весами дуг. Можно показать, что существует константа C, такая что эта задача для произвольного k > 0 может быть решена за время Ck(m + n^1+1/k).

Работа алгоритма Дейкстры проиллюстрирована на рисунке (V = {1, ..., 6}, веса дуг даны в скобках, значения D[v], v О T, приведены со звездочкой (*), минимальные значения - с двумя звездочками.
 
 

 
 
 
 
 
 
 
 

D[1]	D[2]	D[3]	D[4]	D[5]	D[6]
0	1*	╔ *	╔ *	╔ *	╔ *
0	1	6*	3*	╔ *	8*
0	1	4**	3	7*	8*
0	1	4	3	7*	5**
0	1	4	3	6**	5

 

** = min
 
 

Второй случай, для которого известен алгоритм нахождения расстояний от фиксированной вершины за время O(n²) - случай, когда граф является бесконтурным (веса дуг могут быть произвольными). Сначала докажем следующую лемму.

Лемма. В произвольном бесконтурном графе вершины можно перенумеровать так, что каждая дуга будет иметь видб v_i, v_jс, где i < j.

Пример такой нумерации приведен на рисунке.

Для доказательства предложим алгоритм, который конструирует такую нумерацию.
 
 

Алгоритм нумерации вершин бесконтурного графа

Данные: Ориентированный бесконтурный граф <V, E> , определяемый списками инцидентности ЗАПИСЬ [v], v О V.

Результаты: Для каждой вершины v О V номер NR[v], такой что для произвольной дуги б u, vс О E выполняется неравенство NR[u] < NR[v].
 
 

1 begin

2 for v О V do ЧЗАХ [v] := 0;

{ ЧЗАХ [v] = число дуг, заходящих в v }

3 for u О V do

4 for v О ЗАПИСЬ [u] do ЧЗАХ [v] := ЧЗАХ [v] + 1;

5 СТЕК := Ж ;

6 for v О V do

7 if ЧЗАХ [v]= 0 then СТЕКЬ v;

8 num := 0;

9 while СТЕК ╧Ж do

10 begin u Ь СТЕК;

11 num := num + 1; NR[u] := num;

12 for v О ЗАПИСЬ [u] do

13 begin ЧЗАХ [v]:= ЧЗАХ [v] -1;

14 if ЧЗАХ [v]= 0 then СТЕКЬ v;

15 end

16 end

17 end
 
 
 
 

Алгоритм основывается на следующем простом факте: в произвольном (непустом) бесконтурном графе существует вершина, в которую не заходит ни одна дуга. Чтобы убедиться в этом, выберем произвольную вершину w₁ графа, затем некоторую вершину w₂, такую что w_{2 (r)} w₁, затем вершину w₃, такую что w_{3 (r)} w₂, и т.д. Через конечное число шагов мы должны дойти до некоторой вершины w_i, в которую не заходит ни одна дуга, ибо в силу бесконтурности ни одна вершина не может повторяться в последовательности w₁, w₂, w₃ , ... .

В нашем алгоритме вершины, в которые не заходит ни одна дуга, накапливаются в стеке. В строке 10 выбирается верхний элемент стека u (это мог бы быть произвольный элемент стека), и этой вершине присваивается самый маленький из еще неиспользованных номеров. Таким образом, мы гарантируем то, что все дуги, выходящие из этой вершины, ведут к вершине с большими номерами. Затем вершина u вместе с выходящими из нее дугами удаляется из графа. Это приводит к уменьшению на единицу числа дуг, заходящих в каждую вершину v, такую что u(r)  v ; это число запоминается в ЧЗАХ [v]. Если для какой-нибудь из вершин v это число сводится к нулю, то v помещается в стек.

В силу бесконтурности графа и наших предыдущих замечаний полное опустошение стека, вызывающее окончание выполнения алгоритма (см. цикл 9), наступает не раньше, чем после присвоения номеров всем вершинам графа.

Легко заметить, что каждая дуга анализируется алгоритмом один раз в строке 4 и один раз в строке 12. Таким образом, сложность алгоритма есть O(m) (остается в силе предположение m = W (n), в противном случае следовало бы написать O(m + n)).

Примечание:

При сравнении скорости роста двух функций f(n) и g(n) (c неотрицательными значениями) мы, как обычно, используем следующие обозначения:

f(n) = O(g(n)) Ы существуют константы С, N > 0, такие что f(n) ё СЧ g(n) для всех n Ё N

f(n) = W (g(n)) Ы существуют константы С, N > 0, такие что f(n) Ё СЧ g(n) для всех n Ё N.

То есть, в частности, f(n) = W (g(n)) тогда и только тогда, когда g(n) = O(f(n)).
 
 

Согласно вышеизложенному алгоритму при описании алгоритма нахождения путей в бесконтурном графе мы можем предположить, что каждая дуга идет из вершины с меньшим номером в вершину с большим номером.
 
 

Данные: Ориентированный граф <V, E> , где V = {v₁, ... , v_n}, и для произвольной дуги б v_i, v_jс ОE имеем i < j. Этот граф определен списками инцидентности ПРЕДШ[v], v О V.

Результаты: Расстояния от v₁ до всех вершин графа:
 
 

1 begin

2 D[v₁] := 0;

3 for j := 2 to n do D[v_j] := ╔ ;

4 for j := 2 to n do

5 for v_i О ПРЕДШ [v_j] do D[v_j] := min(D[v_j]), D[v_i] + A[v_i, v_j])

6 end
 
 

Нетрудно доказать индукцией по j, что после выполнения цикла 4 для некоторого значения j выполняется равенство D[v_i] = d(v₁, v_i), i = 1, ..., j. Достаточно воспользоваться тем фактом, что все промежуточные вершины кратчайшего пути из v₁ в v_i имеют номера меньше j.

Сложность алгоритма порядка O(m), так как каждая дуга б v_i, v_jс анализируется а строке 5 в точности один раз.

Описанные алгоритмы находят применения, в частности, в методах управления выполнением проекта, называемых PERT (Project Evaluation and Review Technique) или CPM  (Critical Path Method). Эти методы основываются на построении графа (сети PERT или сети CPM), дуги которого соответствуют некоторым элементарным задачам, составляющим проект, а их веса указывают на время, необходимое для решения отдельных задач.

Кроме этого, мы предполагаем, что для произвольных дуг этого графа б u, vси бv, tс задача, изображаемая дугой б u, vс, должна быть закончена перед началом решения задачи, изображаемой дугой бv, tс .

Легко заметить, что такой граф должен быть бесконтурным. Нашей задачей является нахождение самого длинного пути из вершины s, соответствующей началу проекта, до вершины t, соответствующей его окончанию. Такой путь называется критическим путем. Его длина определяет время, необходимое для реализации всего проекта. Очевидно, что задача сводится к задаче о кратчайшем пути путем изменения знака каждого веса a(u, v), где u (r)  v, на обратный.
 
 

Очевидно, что задачу определения расстояния между всеми парами вершин можно решить, используя n раз (поочередно для каждой вершины) один из ранее изложенных методов нахождения расстояний от фиксированной вершины. Таким образом, мы получаем алгоритм со сложностью O(n⁴) (при использовании метода Форда - Беллмана) или O(n³) для бесконтурных графов или неотрицательных весов. Однако оказывается, что в общем случае n-кратное использование метода Форда - Беллмана не является наилучшим методом. Рассмотрим два более эффективных метода.

Для этого рассмотрим ориентированный граф G = < V, E>, где V = {v₁, ..., v_n}, и предположим, что A = [a_ij] есть матрица весов (a_ij = a(v_i, v_j)). Обозначив через d_ij^(m) длину кратчайшего пути из v_i  в v_j, содержащего не более m дуг, получаем следующие очевидные уравнения:

(1)

d_ij^(m+1) = min{d_ik^(m) + a_kj : 1<k<n}. (2)

Из уравнений (1) и (2) теперь легко следует, что [d_ij⁽⁰⁾ = U] и

(1) d_ij^(n-1) = d_ij⁽ⁿ⁾ и в результате d_ij^(m) = d_ij^(n-1) для каждого m Ё  n. Тогда очевидно d_ij^(n-1) = d(v_i, v_j).

(2) d_ij^(n-1) ╧ d_ij⁽ⁿ⁾ . Это означает, что существует контур отрицательной длины.

Произведение A*B двух матриц размерности n ╢ n можно вычислить за время O(n³) (n сложений и n - 1 сравнений на каждый из n² элементов произведения A*B). Следовательно, матрицу [d_ij^(n-1)] и тем самым расстояние между всеми парами вершин можно вычислить за время O(n⁴).

Пока сложность этого алгоритма такая же, как и для случая n-кратного использования алгоритма Форда - Беллмана. Однако мы можем ее снизить, если заметим, что операция * ассоциативна (т.е. (A * B) * C = A * (B * C)). Этот факт позволяет вычислять произведение (3), поочередно возводя матрицу A в квадрат и тем самым заменяя n - 1 умножение матрицы й log nщ умножениями. Таким образом, мы получаем алгоритм сложности O(n³ log n), отыскивающий расстояния между всеми парами вершин в графе без контуров отрицательной длины.

Авторами еще более эффективного алгоритма являются Уоршалл и Флойд. Идея этого алгоритма следующая. Обозначим через d_ij^(m) длину кратчайшего из путей из v_i  в v_j с промежуточными вершинами в множестве {v₁, ..., v_m}.

Тогда имеем следующие уравнения:

Если же он содержит v_m+1, то деля путь на отрезки от v_i до v_m+1 и от v_m+1 до v_j, получаем равенство d_ij^(m+1) = d_im^(m) +d_mj^(m).

Уравнения (4) и (5) дают возможность легко вычислить расстояния d(v_i, v_j) = d_ij⁽ⁿ⁾, 1 ё  i, j ё n.
 
 

Данные: Матрица весов дуг A[i, j], 1 ё  i, j ёn, ориентированного графа без контуров отрицательной длины.

Результаты: Расстояния между всеми парами вершин D[i, j] = d(v_i, v_j).

1 begin

2 for i := 1 to n do

3 for j := 1 to n do D[i, j] := A[i, j];

4 for i := 1 to n do D[i, i] := 0;

5 for m := 1 to n do

6 for i := 1 to n do

7 for j := 1 to n do

8 D[i, j] := min(D[i, j], D[i, m] + D[m, j];

9 end
 
 

Очевидно, что сложность этого алгоритма есть O(n³). Отметим, что такую же сложность имел алгоритм Форда - Беллмана нахождения расстояний от фиксированной вершины до всех остальных вершин. Любопытно, что для общего случая (т.е. без предположения о неотрицательности весов либо о бесконтурности графа) не известен ни один алгоритм нахождения расстояния между одной фиксированной парой вершин, который был бы значительно эффективнее алгоритма нахождения расстояний между всеми парами вершин.

С задачей определения кратчайших путей в графе тесно связана задача транзитивного замыкания бинарного отношения. Вспомним, что под бинарным отношением на множестве V мы понимаем произвольное подмножество E Н V╢ V. Такое отношение является транзитивным, если выполняется условие
 
 

для произвольных x, y, z О E. Заметим, что бинарное отношение E Н V╢ V можно однозначно представить ориентированным графом G = <V, E> . Для произвольного такого отношения мы определяем

E^* = { б x, yс: в <V, E> существует путь ненулевой длины из x в y}.

Нетрудно заметить, что E^* - транзитивное отношение на множестве V и E Н E^*. Более того, E^* является наименьшим транзитивным отношением, содержащим E, т.е. для произвольного транзитивного отношения F КE выполняется включение E^*Н F. Отношение E^* называется транзитивным замыканием отношения E.

Если отношение E представить в виде графа <V, E>, в котором каждая дуга имеет вес 1, то транзитивное замыкание E^* можно вычислить с помощью алгоритма Флойда за время O(n³); после завершения работы имеем

< v_i, v_{j >}О E^* Ы D[i, j] < ╔ .

При вычислении транзитивного замыкания удобно принять

(6)

D[i, j] := D[i, j] Ъ (D[i, m] Щ D[m, j] ),

где Ъ и Щ - обычные булевы операции.

После завершения работы алгоритма, модифицированного таким образом (принадлежащего Уоршаллу), очевидно, имеем
 
 

Известен алгоритм построения транзитивного замыкания, более эффективный, чем алгоритм Уоршалла. Он использует связь этой задачи с умножением матриц, обсуждавшуюся ранее, эта связь для матриц A, определяемых равенством (6), приводит к обычному умножению булевых матриц по формуле
 
 

Такое умножение можно выполнить за время O(n^{log 7}), что дает алгоритм построения транзитивного замыкания, имеющего сложность O(n^{log 7} log n). Такой алгоритм имеет скорее теоретическое значение, поскольку метод умножения матриц за время O(n^{log 7}) является довольно сложным и, следовательно, обнаруживает свое преимущество перед обычным ╚школьным╩ методом только при очень больших значениях n. На практике обычно самым эффективным оказывается алгоритм Уоршалла, соответствующим образом запрограммированный.

Другим способом построения транзитивного замыкания отношения E является применение поиска в глубину (или в ширину) в графе <V, E> . Этот способ особенно выгоден, когда отношение E симметрично; очевидно, что тогда транзитивное замыкание строится отдельно для каждой связной компоненты, на которые разбивается неориентированный граф, определяемый отношением E, и это построение может быть получено за время O(m + n).