Алгоритм Флойда — Уоршелла для всех пар

Иногда нужно найти кратчайший путь между каждой парой вершин, а не только от одной исходной вершины. Это задача поиска кратчайших путей между всеми парами.

Алгоритм Флойда — Уоршелла заполняет полную таблицу расстояний для всех пар с помощью трёх аккуратных вложенных циклов и почти без предварительной настройки.

Используйте матрицу, в которой dist[i][j] — наилучшая известная стоимость пути из i в j. Изначально заполните её заданными прямыми рёбрами.

Каждая вершина достигает саму себя бесплатно, поэтому перед началом релаксации установите диагональные элементы dist[i][i] равными нулю.

Приём заключается в следующем: разрешите путям проходить через промежуточную вершину k, а затем проверьте, не будет ли маршрут через k дешевле прямого пути.

Внешним должен быть цикл по k — выбранной промежуточной вершине. Внутренние циклы по i и j проверяют каждую пару относительно этой вершины.

Для каждой пары выполните релаксацию через k: если путь из i в k, а затем из k в j короче, обновите dist[i][j] этой суммарной стоимостью.

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

Алгоритм Флойда — Уоршелла допускает отрицательные рёбра, но не отрицательные циклы. Отрицательный цикл оставляет некоторый диагональный элемент меньше нуля.

Три цикла по n вершинам дают время O(n^3) и расход памяти O(n^2), поэтому алгоритм практически применим только при n в несколько сотен.

Выбирайте алгоритм Флойда — Уоршелла, когда граф небольшой и плотный и Вам действительно нужны расстояния между всеми парами, а не только расстояния от одной исходной вершины.

Какой цикл должен быть внешним в алгоритме Флойда — Уоршелла?

Инициализируйте матрицу, установите нули на диагонали, затем запустите циклы k, i, j и выполните релаксацию через k. Кратчайшие пути между всеми парами за O(n^3). 🧮