Флойд — Уоршелл: кратчайшие пути между всеми парами

Интерактивный разбор Флойда — Уоршелла: https://grundyjs.ru/algorithms/floyd-warshall/?utm_source=rutube&utm_medium=social&utm_campaign=floyd_warshall&utm_content=horizontal Флойд — Уоршелл находит минимальную стоимость путей сразу между всеми парами вершин. В матрице строка задаёт начало, столбец — конец. На каждом этапе разрешаем ещё одну промежуточную вершину k и проверяем d(i,j) = min(d(i,j), d(i,k) + d(k,j)). В примере прямой путь A → D стоит 10. Через B получается 3 + 6 = 9. Через C — маршрут A → B → C → D стоимостью 3 + (−2) + 2 = 3. Ячейки одного этапа обновляются вместе из предыдущего слоя матрицы. Обратного пути D → A здесь нет: ∞ означает недостижимость. Если все веса равны единице, минимальная стоимость совпадает с минимальным числом рёбер. В этом примере прямое ребро A → D тогда даёт стоимость 1. Отрицательные рёбра допустимы. Отрицательное число на диагонали после основных этапов указывает на отрицательный цикл. Цикл B → C → B стоит −2 + 1 = −1. Для пар, чей маршрут может пройти через такой цикл, конечного минимума нет: −∞. Остальные ответы сохраняются. Время O(V³), матрицы расстояний и восстановления маршрутов занимают O(V²). В интерактивном примере можно менять веса, выбирать пару вершин и смотреть этапы алгоритма, а также поделиться ссылкой на свой граф. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #ФлойдУоршелл #графы #программирование