Алгоритм следует из выражения 5.1

for k =1 to | V | do

for i =1 to | V | do

for j =1 to | V | do

a_ija_ij Ú a_ik Ù a_kj

Упражнения:

1.Заметим, что в алгоритме 2, основанном на выражении 5.1, элементы матрицы А ^{( k -1)} непосредственно преобразуются в элементы матрицы А ^{( k )}, то есть не используется дополнительная память для хранения элементов матрицы А ^{( k -1)}. Докажите, что такая реализация выражения 5.1 корректна.

2. Очевидно, что трудоемкость алгоритма нахождения транзитивного замыкания O(| V |³). Представьте строки матрицы А в битовой форме и снизьте трудоемкость алгоритма до O(| V |²). Реализуйте оба варианта алгоритма и сравните время их работы.

3. Реализуйте алгоритм нахождения матрицы достижимости на основе использования стратегии поиска в глубину или ширину и сравните время работы этого алгоритма с временем работы алгоритма нахождения транзитивного замыкания.

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

Указание. Для хранения путей используйте матрицу P размера n ´ n, где n – число вершин графа. Элементы матрицы можно определить одним из двух способов:

1) P_ij – вершина, предшествующая вершине j на пути из вершины i в вершину j;

2) P_ij – вершина, следующая за вершиной i на пути из вершины i в вершину j.