Алгоритм Флойда
Алгоритм Флойда вычисляет длины кратчайших путей между всеми парами вершин взвешенного графа. Он работает с матрицей расстояний и последовательно разрешает использовать всё больше промежуточных вершин.
Вначале строят таблицу кратчайших расстояний: на диагонали записывают \(0\), для непосредственного ребра — его вес, а при отсутствии ребра — условно бесконечность. Затем вершины по очереди становятся разрешёнными промежуточными вершинами.
Здесь \(d_{ij}^{(k)}\) — кратчайшее расстояние из вершины \(i\) в вершину \(j\), если в качестве промежуточных разрешены первые \(k\) вершин. На каждом шаге проверяется: выгоднее оставить прежний путь или пройти через вершину \(k\).
Пусть прямой путь из \(A\) в \(C\) имеет длину \(10\), а рёбра \(A\to B\) и \(B\to C\) имеют длины \(3\) и \(4\). Когда \(B\) рассматривается как промежуточная вершина, алгоритм сравнивает \(10\) и \(3+4\) и записывает \(d(A,C)=7\). Так постепенно уточняются расстояния для всех пар.
Кратчайший путь от одной вершины ко всем остальным обычно ищут алгоритмом Дейкстры. Алгоритм Флойда сразу решает задачу для всех пар, но требует \(O(n^3)\) операций. Он допускает отрицательные веса рёбер, если в графе нет цикла отрицательного веса.
Что сравнивается на каждом шаге алгоритма Флойда?
Главное
- Алгоритм Флойда находит расстояния между всеми парами вершин.
- Основа метода — обновление \(d_{ij}=\min(d_{ij},d_{ik}+d_{kj})\).
- Сложность равна \(O(n^3)\); отрицательные рёбра допустимы при отсутствии отрицательных циклов.