Алгоритм Уоршелла

Описан простой алгоритм транзитивного замыкания отношения на множестве {a,b,c,d}. Изображается соответствующий граф и дополнительные дуги, возникающие после замыкания графа на свойство транзитивности.

[@deadrunner983]

Спасибо огромное! Ваше объяснение очень доходчиво и сохранило мне много времени и нервов

[@vasiapunkrok]

Спасибо! Четко, ясно, понятно, быстро! Не то, что на лекциях: по полтора часа объясняют, но ничего не понятно

[@YuliiaJV]

Спасибочки! Пишу расчетку по дискретке и страдаю, но ві мне облегчили страдания)

[@1ROMARIO1985]

Спасибо Вам огромное, за Ваш труд.

[@ms.maria.golubeva]

Спасибо большое! Все очень понятно и доступно!❤️

[@oksanakost3355]

Спасибо большое! Все очень доступно и понятно!

[@sirilliya]

Большое спасибо! Все просто и понятно!

[@bwnuts]

Спасибо большое, хоть расчетку до полуночи закончу

[@ayananygmetova5681]

спасибо большое, очень понятно и доступно

[@bobhutchinson3638]

Все понятно! Спасибо!

[@by_bbdm4881]

Преподаватель от Бога, спасибо!

[@user-kg7pu3mr1l]

Шикарно обьясняет

[@user-gn7nd3md1b]

Спасибо!!

[@user-nl9nh4yj9u]

Спасибо!

[@userasdf123]

Круто !

[@jeremyclarkson3209]

Спасибо!!!

[@andriyburtso7591]

Спс

[@1CrazyTeamChannel]

Четко, все понятно, like

[@Vitgic]

на 6.06 минуте подзамкнуло у меня

[@user-lg7bh5dn1i]

а почему к 4 строке не добавили 1 в столбце b?

[@Kirsanov2011]

Спасибо, Лена! Действительно, пропустил 1. Иначе путь d->a->b не сокращается до d->b

[@sovaz1997]

Можно сделать проще:
for(int k = 0; k < N; ++k) {
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}

[@Kirsanov2011]

+Олег Смирнов Спасибо!

[@nuki7944]

музька в начале как в голливудском фильме

[@Kirsanov2011]

Это кусочек гимна МЭИ...

[@dotdiese8380]

Мне не понятно, зачем вы поменяли значение в (d,d), если он находится на диагонали??

[@iMaxBlazer]

Потому что диагональ мы не трогали в исходной матрице. В заполнении результирующей таблицы нет никаких дополнительных правил.

[@mesmeridze1]

Если честно, понятней для меня не стало :) Шаг на d,d избыточен, он не добавляет транзитивности ни для одного элемента.

[@iMaxBlazer]

d доступна сама для себя через а, поэтому добавляем петлю.Oleksandr Znachkov

[@danya151mail]

iMaxBlazer в транзитивности три Разных элемента присутствуют

[@hytryi_huy]

У мене от взагалі метро нема, пересадку спробував у Києві і це геніально, сідаєш в метро і забуваєшся

[@Kirsanov2011]

Приїжджай в Москву. Тут цікаво. Нові станції майже кожен місяць з'являються. Спасибі Собяніну. І поїзда суперкомфортні.

[@kovbaska_]

@@Kirsanov2011 згодом

[@aelfwynnx]

@@Kirsanov2011 ахаххаха хороший жарт

[@user-on4oi7cr6r]

Либо я делаю что-то не так, либо алгоритм не сходится на примере
Входные данные:
0 1 0 0
0 0 0 1
0 0 0 0
1 0 1 0
Выходные данные должны быть:
1 1 1 1
1 1 1 1
0 0 0 0
1 1 1 1
А у меня когда я делал я складывал первую строчку со второй и у меня получилось [0 1 0 1] что уже не сходится

[@Kirsanov2011]

Это итеративный алгоритм. Повторите, но уже по измененной матрице. Все получится!

[@user-on4oi7cr6r]

@@Kirsanov2011 Спасибо) Я кстати сдал предмет на 5 ещё где-то в июне))

[@arthurrebar6693]

@@Kirsanov2011 а как узнать итеративный ли алгоритм??