Где применяется
1. Задача
Прошлый урок (Беллман-Форд, шаг 99) и Дейкстра (шаг 97) отвечают на один вопрос: как далеко от ОДНОГО стартового узла до всех остальных? Один запуск даёт одну строку расстояний.
Иногда нужна вся таблица: расстояние от каждого места до каждого другого. Например, у курьерского склада 40 точек, где забирают посылки. Склад хочет знать цену пути между любыми двумя точками, чтобы по запросу сразу строить любой маршрут. Стартовых точек здесь n, и ответ это сетка n на n.
Можно запустить Дейкстру по разу из каждого узла. Флойд-Уоршелл заполняет всю сетку одним коротким тройным циклом (три цикла, вложенные друг в друга). Код остаётся простым, когда граф маленький и плотный, то есть рёбер в нём много.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где нужно кратчайшее расстояние между каждой парой вершин или ответ, кто до кого может дойти, на графе из нескольких сотен вершин или меньше. Три вложенных цикла с промежуточной вершиной снаружи заполняют всю таблицу за n^3 шагов.
- 1334.Find the City With the Smallest Number of Neighbors at a Threshold Distance (откроется в новой вкладке)Средняя
n не больше 100, так что один раз прогони тройной цикл, а потом для каждого города посчитай, сколько других лежит в пределах порога.
Замени min и плюс на OR и AND, и тот же цикл скажет для каждой пары курсов, нужен ли один для другого.
Вершины здесь это 26 букв, таблица 26 на 26, и каждая позиция строки потом стоит одного обращения к ней.
Каждое уравнение это ребро с отношением, и путь через промежуточную переменную перемножает два отношения там, где в уроке складываются две стоимости.