Как алгоритмом Флойда-Уоршелла найти кратчайшие пути между всеми парами вершин?
Граф маленький (n <= 500), но нужны расстояния между ВСЕМИ парами вершин, плюс могут быть отрицательные рёбра. Запускать Дейкстру из каждой вершины не хочется писать. Слышал про Флойда-Уоршелла — как он работает и почему три вложенных цикла?
2 ответа
Флойд-Уоршелл — динамика. dist[i][j] после обработки вершины k = кратчайший путь из i в j, использующий промежуточные вершины только из {0..k}. Внешний цикл по k (какие вершины разрешены как промежуточные), внутри — пробуем «пройти через k».
using ll = long long;
const ll INF = 1e18;
// dist[i][j] инициализирован весами рёбер, dist[i][i]=0, нет ребра = INF
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] < INF && dist[k][j] < INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
Сложность O(V³) по времени, O(V²) по памяти. Порядок циклов критичен: k обязан быть внешним. Работает с отрицательными рёбрами; отрицательный цикл детектируется по dist[i][i] < 0 для какого-то i.
Грабля с порядком: если поставить k во внутренний цикл — алгоритм сломается, потому что нарушится инвариант динамики (вы используете k как промежуточную раньше, чем досчитали пути через неё). Ещё проверка dist[i][k] < INF && dist[k][j] < INF спасает от переполнения INF + INF. И помните про память: при n = 2000 матрица long long это уже ~32 МБ, может не влезть — тогда Флойд не подходит, берите Дейкстру/Джонсона из каждой вершины.