Страницы

Поиск по вопросам

понедельник, 15 октября 2018 г.

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

По матрице смежности нужно построить матрицу достижимости. Использую Алгоритм Флойда — Уоршелла:
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) Где ошибка?


Ответ

Никакой ошибки нет.
Посмотрите внимательно на граф: Из узлов 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
Если вам для задачи этой информации не требуется, то после работы алгоритма можно пробежаться по диагональным элементам и проставить единички.

Комментариев нет:

Отправить комментарий