Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

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

Дан граф - весовая матрица
Необходимо найти кратчайшие расстояния между всеми парами вершин

Алгоритм работает корректно на графах, не содержащих циклов отриц. веса, кратных рёбер и петель.
Асимптотика O(N³).

Листинг C++

void floyd (vector < vector < int > > &D
            vector < vector < int > > &P)
{
   for (int k = 0; k < n; ++ k)
        for (int i = 0; i < n; ++ i)
            for (int j = 0; j < n; ++ j)
            {
                D[i][j] = min (D[i][j], D[i][k] + D[k][j]);
                P[i][j] = k;
            }
}