355
правок
Изменения
Нет описания правки
for j = 1 to n
W[i][j] = W[i][j] or (W[i][k] and W[k][j])
=== Доказательство === <wikitex>Назовем ''промежуточной'' вершину некоторого пути $p = \left \langle v_0, v_1, \dots, v_k \right \rangle$, принадлежащую множеству вершин этого пути и отличающуюся от начальной и конечной вершин, то есть принадлежащую $\left \{ v_1, v_2, \dots, v_{k-1} \right \}$</wikitex>
=== Сложность алгоритма ===
Три вложенных цикла работают за время <tex>\sum\limits_{n}\sum\limits_{n}\sum\limits_{n}O(1) = O(n^3)</tex>,
