Алгоритм Флойда
Перейти к навигации
Перейти к поиску
TLDR
Код
Ищем расстояния во взвешенном графе от каждой вершины до всех остальных. Веса могут быть любыми.
Идея алгоритма:
- Инициализация. Пусть dist[a][b] — кратчайшее расстояние от a до b, но длиной не более чем одно ребро. Нетрудно понять, что dist — это просто матрица смежности графа (возможно, с небольшими модификациями):
- Случай простого графа: dist[a][a] = 0, dist[a][b] = весу ребра (a, b); если ребра (a, b) нет, то dist[a][b] = INF;
- Если есть кратные рёбра, то dist[a][b] = весу минимального ребра между a и b;
- Если есть петли, то dist[a][a] = min(0, вес минимальной петли из a);
- Шаг 0. Теперь разрешаем путям проходить через вершину 0. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][0] + dist[0][b]);
- Шаг 1. Теперь разрешаем путям проходить через вершину 1. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][1] + dist[1][b]);
- Повторяем до шага vertexCount - 1.
const int INF = 1e9;
vector<vector<int>> dist(vertexCount, vector<int>(vertexCount, INF));
for (int v = 0; v < vertexCount; v++)
dist[v][v] = 0;
for (int i = 0; i < edgeCount; i++) {
int a, b, w;
cin >> a >> b >> w;
dist[a][b] = min(dist[a][b], w);
}
for (int v = 0; v < vertexCount; v++) {
for (int a = 0; a < vertexCount; a++) {
for (int b = 0; b < vertexCount; b++) {
if (dist[a][v] == INF || dist[v][b] == INF)
continue;
dist[a][b] = min(dist[a][b], dist[a][v] + dist[v][b]);
dist[a][b] = max(dist[a][b], -INF);
}
}
}
На что нужно обратить внимание:
- При инициализации матрицы на главной диагонали должны быть нули (если нет петель отрицательного веса), а там, где рёбер нет — бесконечности;
- При наличии отрицательных рёбер следует избегать присваиваний вида (INF - 1). Для этого, если хотя бы один из фрагментов пути равен INF, нужно делать continue;
- При наличии отрицательных циклов расстояния могут очень быстро уменьшаться и приводить к отрицательным переполнениям. Поэтому нужно ограничивать отрицательные числа снизу.
Отрицательные циклы
Вершина v лежит на отрицательном цикле, если после запуска алгоритма Флойда dist[v][v] < 0. Наличие такой вершины — критерий отрицательного цикла в алгоритме Флойда.
При наличии отрицательных циклов между некоторыми парами вершин может не существовать кратчайшего пути. Между вершинами a и b нет кратчайшего пути, если существует вершина v, лежащая на отрицательном цикле, которая достижима из a и из которой достижима b.
const int NO_SHORTEST_PATH = -2e9;
for (int v = 0; v < vertexCount; v++)
for (int a = 0; a < vertexCount; a++)
for (int b = 0; b < vertexCount; b++)
if (dist[a][v] != INF && dist[v][v] < 0 && dist[v][b] != INF)
dist[a][b] = NO_SHORTEST_PATH;
Ссылки
Теория:
- e-maxx.ru — Алгоритм Флойда-Уоршелла
- cp-algorithms.com — Floyd-Warshall Algorithm
- neerc.ifmo.ru/wiki — Алгоритм Флойда
- brestprog.by — Алгоритм Флойда-Уоршелла
- algorithmica.org — Кратчайшие пути в графе
- brilliant.org — Floyd-Warshall Algorithm
- usaco.guide — Shortest Paths with Non-Negative Edge Weights: Floyd-Warshall, Shortest Paths with Negative Edge Weights: Floyd-Warshall
Демонстрация:
Код:
- indy256/codelibrary/java/graphs/shortestpaths/FloydWarshall.java
- ADJA/algos/Graphs/FloydWarshall.cpp
- kevin-wayne/algs4/FloydWarshall.java
Задачи: