Алгоритм Флойда

Ищем расстояния во взвешенном графе от каждой вершины до всех остальных. Веса могут быть любыми.

Идея алгоритма:

• Инициализация. Пусть 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]);
• Повторяем до шага n - 1.

vector<vector<int>> g(n, vector<int>(n));
vector<vector<int>> dist(n, vector<int>(n));
const int INF = 1e9;

// считаем, что петель и кратных рёбер нет, граф задан матрицей смежности g, g[a][b] == 0 --- признак отсутствия ребра
for (int a = 0; a < n; a++) {
   for (int b = 0; b < n; b++) {
       if (a == b)
           dist[a][b] = 0;
       else
           dist[a][b] = (g[a][b] ? g[a][b] : INF);
    }
}

for (int v = 0; v < n; v++) {
    for (int a = 0; a < n; a++) {
        for (int b = 0; b < n; b++) {
            if (dist[a][v] == INF || dist[v][b] == INF)
                continue;
            dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b]);
            dist[a][b] = min(dist[a][b], -INF);
        }
    }
}

На что нужно обратить внимание:

• При инициализации матрицы на главной диагонали должны быть нули (если нет петель отрицательного веса), а там, где рёбер нет — бесконечности;
• При наличии отрицательных рёбер следует избегать присваиваний вида (INF - 1). Для этого, если хотя бы один из фрагментов пути равен INF, нужно делать continue;
• При наличии отрицательных циклов расстояния могут очень быстро уменьшаться и приводить к отрицательным переполнениям. Поэтому нужно ограничивать отрицательные числа снизу.

Ссылки на задачи

• ACMP #135 — Алгоритм Флойда
• ACMP #136 — Алгоритм Флойда - 2
• ACMP #137 — Существование пути
• ACMP #562 — Слабая K-связность

Ссылки

• e-maxx.ru — Алгоритм Флойда-Уоршелла
• neerc.ifmo.ru/wiki — Алгоритм Флойда
• brestprog — Алгоритм Флойда-Уоршелла
• algorithmica.org — Кратчайшие пути в графе
• Brilliant.org — Floyd-Warshall Algorithm
• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 5
• CodeLibrary — Floyd–Warshall algorithm
• Algos — Floyd–Warshall algorithm