Матрица достижимости

#алгоритм

По матрице смежности нужно построить матрицу достижимости. Использую Алгоритм Флойда
— Уоршелла: 

for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                W[i][j] = (W[i][j] || (W[i][k] && W[k][j]));


На графе  

0 1 0 0 0  
0 0 0 1 0  
0 1 0 0 0  
0 0 1 0 0  
1 0 1 1 0  


Данный алгоритм выдает:  

0 1 1 1 0  
0 1 1 1 0  
0 1 1 1 0  
0 1 1 1 0  
1 1 1 1 0  


Но на сайте у них получилась немного другая матрица. T(D)
Где ошибка?
    

Ответы

Ответ 1

Никакой ошибки нет.

Посмотрите внимательно на граф:

Из узлов 2 3 4 можно добраться "из себя в себя" по некоторому пути.
А из узлов 1 и 5 "в себя" не доберёшься.
Поэтому такая матрица и получается:

0 1 1 1 0  
0 1 1 1 0  
0 1 1 1 0  
0 1 1 1 0  
1 1 1 1 0  


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