7. Алгоритм Флойда Уоршелла
В статьях 5. Кратчайшие пути. Алгоритм Дейкстры и 6. Алгоритм Беллмана Форда мы решали задачу поиска кратчайших путей от одной стартовой вершины ко всем остальным (Single-Source Shortest Path).
Но что если архитектура вашей распределенной системы требует мгновенно знать кратчайшие расстояния между всеми парами узлов сразу? Например:
- Вы проектируете сетевой протокол динамической маршрутизации (BGP или OSPF), где каждый роутер обязан хранить полную матрицу задержек (Latency Matrix) до любой другой точки автономной системы.
- Вы строите логистический координатор для маркетплейса, которому нужно за доли миллисекунды рассчитывать стоимость перемещения грузов между любыми двумя складами из сотен доступных.
Запускать алгоритм Дейкстры по очереди для каждой из $V$ вершин — долго, а запускать Беллмана-Форда $V$ раз — непозволительно дорого с вычислительной точки зрения ($O(V^2 E)$).
Для решения этой задачи применяется признанный шедевр динамического программирования — Алгоритм Флойда-Уоршелла (Floyd-Warshall Algorithm), сформулированный Робертом Флойдом и Стивеном Уоршеллом в 1962 году.
Механика алгоритма: Сила промежуточной вершины
Алгоритм Флойда-Уоршелла решает задачу поиска кратчайших путей между всеми парами вершин (All-Pairs Shortest Path) за строго определенное время $O(V^3)$. Он корректно обрабатывает ребра с отрицательными весами и безошибочно выявляет наличие отрицательных циклов.
Идея алгоритма до гениальности лаконична. Возьмем любые две произвольные вершины $i$ и $j$. Зададимся естественным вопросом:
«Станет ли маршрут из $i$ в $j$ короче, если мы пройдем его транзитом через некоторую промежуточную вершину $k$?»
Если суммарная дистанция пути $i \to k$ плюс пути $k \to j$ оказывается меньше, чем известный на данный момент прямой путь $i \to j$, мы обновляем наше знание о лучшем маршруте.
Математическая формула перехода (релаксации) выглядит предельно просто:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
flowchart TD
I["Вершина I"] -->|"Прямой путь: 10"| J["Вершина J"]
I -->|"Путь в K: 3"| K["Вершина K<br>★ Промежуточная"]
K -->|"Путь из K: 4"| J
classDef default fill:#131d33,stroke:#38bdf8,stroke-width:1.5px,color:#f8fafc;
classDef transit fill:#991b1b,stroke:#f87171,stroke-width:2px,color:#ffffff;
class K transit;
На диаграмме прямой путь равен 10. Но путь через транзитный узел K равен 3 + 4 = 7. Мы выбираем транзит.
Mechanical Sympathy: Почему O(V³) работает быстро?
Чистая асимптотика способна испугать любого бэкендера: кубическая сложность $O(V^3)$ означает, что для графа из $1\,000$ вершин алгоритму потребуется выполнить $1\,000\,000\,000$ (один миллиард) итераций. Кажется, что сервер немедленно уйдет в глухой троттлинг.
Но с точки зрения физики современного «железа», Флойд-Уоршелл — один из самых любимых и дружелюбных алгоритмов для процессора:
- Он работает на Матрице смежности (см. 1. Представление графов).
- В нем нет сложных ветвлений (Branching) — только элементарное сложение и инструкция минимума (
CMOVна x86). Предсказатель ветвлений (Branch Predictor) практически не ошибается. - В нем идеальная кэш-локальность (Spatial Locality). Внутренний цикл по
jчитает строку матрицы строго последовательно:dist[i][0],dist[i][1],dist[i][2]. Аппаратный Prefetcher процессора подтягивает 64-байтные строки L1/L2 кэша на максимальной скорости шины.
Один миллиард тактов на современном CPU с частотой 4 ГГц (где инструкции конвейеризуются и выполняются в режиме Out-of-Order) отрабатывает за доли секунды!
Production-Ready реализация на Go
Реализуем алгоритм с плоской матрицей и защитой от переполнений:
package main
import (
"errors"
"math"
)
var ErrNegativeCycleFW = errors.New("граф содержит отрицательный цикл")
// FloydWarshall принимает список ребер и возвращает плоскую матрицу расстояний
func FloydWarshall(vertices int, edges []struct{ u, v, weight int }) ([]int64, error) {
if vertices <= 0 {
return nil, nil
}
// 1. Инициализация плоской матрицы V x V
dist := make([]int64, vertices*vertices)
// Константа бесконечности с запасом от переполнения
const INF = math.MaxInt64 / 2
for i := range dist {
dist[i] = INF
}
// Расстояние от узла до самого себя равно 0
for i := 0; i < vertices; i++ {
dist[i*vertices+i] = 0
}
// Загружаем начальные ребра
for _, edge := range edges {
// Если между узлами несколько ребер, берем минимальное
idx := edge.u*vertices + edge.v
if int64(edge.weight) < dist[idx] {
dist[idx] = int64(edge.weight)
}
}
// 2. Основная логика: Три вложенных цикла
// ВНЕШНИЙ ЦИКЛ — транзитная вершина K
for k := 0; k < vertices; k++ {
for i := 0; i < vertices; i++ {
// Оптимизация: если пути от I до K нет, внутренний цикл не нужен
ik := dist[i*vertices+k]
if ik == INF {
continue
}
for j := 0; j < vertices; j++ {
kj := dist[k*vertices+j]
if kj == INF {
continue
}
ij := i*vertices + j
newDist := ik + kj
if newDist < dist[ij] {
dist[ij] = newDist
}
}
}
}
// 3. Проверка на отрицательные циклы
// Если путь от вершины до нее самой стал меньше 0 — это отрицательный цикл
for i := 0; i < vertices; i++ {
if dist[i*vertices+i] < 0 {
return nil, ErrNegativeCycleFW
}
}
return dist, nil
}
Паттерны задач и собеседований
1. Транзитивное замыкание (Алгоритм Уоршелла)
Иногда нам не требуется знать точные числовые дистанции, а нужно лишь ответить на вопрос: достижима ли вершина $J$ из вершины $I$ (Reachability)? Это называется Транзитивным замыканием графа.
В этом случае алгоритм предельно упрощается:
- Матрица
distзаменяется на булевуreachable []bool. - Сложение заменяется логическим «И» (
&&). - Поиск минимума заменяется логическим «ИЛИ» (
||).
Формула релаксации:
reachable[i][j] = reachable[i][j] || (reachable[i][k] && reachable[k][j])
2. Восстановление пути
Как восстановить не только длину кратчайшего пути, но и саму цепочку переходов?
Как и в алгоритме Дейкстры, мы заводим вспомогательную матрицу предков или матрицу переходов next [][]int (или плоский массив []int размера $V \times V$).
Ячейка next[i][j] сохраняет следующую промежуточную вершину, в которую нужно шагнуть из $i$ по пути в $j$. При каждой успешной релаксации (когда маршрут через $k$ оказался короче):
next[i][j] = next[i][k]
Временная и пространственная сложность
- Временная сложность: строго $O(V^3)$. Алгоритм детерминирован и выполняет три вложенных цикла фиксированное число раз.
- Пространственная сложность: $O(V^2)$ для хранения матрицы смежности. Для графов с более чем 10 000 вершинами потребуется свыше $800$ МБ RAM (
10000 * 10000 * 8 байт), поэтому алгоритм применим только для относительно плотных или небольших графов.
Итог
- Алгоритм Флойда-Уоршелла — ищет кратчайшие пути между всеми парами вершин.
- Базируется на динамическом программировании и попытке проложить маршрут через каждую возможную транзитную вершину $K$ (внешний цикл!).
- Обладает идеальной Mechanical Sympathy благодаря линейному проходу по памяти и отсутствию ветвлений, что делает его константу под $O(V^3)$ экстремально малой.
- Умеет находить отрицательные циклы, проверяя главную диагональ матрицы: если расстояние от узла до самого себя стало меньше $0$ — найден отрицательный цикл.
Мы закончили блок алгоритмов, которые ищут пути (в глубину, ширину и кратчайшие). Но графы таят в себе и другие секреты. Что если нам нужно не добраться из точки А в точку Б, а проложить кабель между всеми серверами в дата-центре так, чтобы суммарная длина кабеля была минимальной, и при этом не было колец (циклов)? Эта задача называется построением остова, и мы разберем её в следующей статье: 8. Минимальное остовное дерево. Алгоритм Крускала.