Информатика. Теория графов: Алгоритм Флойда. Центр онлайн-обучения «Фоксфорд»

• Алгоритм Флойда позволяет находить кратчайшие пути из каждой вершины графа в каждую, с учетом отрицательных весов ребер.  

• Алгоритм является динамическим программированием и работает с таблицами, которые заполняются по мере продвижения по графу.  

• Время работы алгоритма составляет O(V^3), где V - количество вершин в графе.  

• Для хранения графа и смежности требуется O(V^3) памяти.  

• Если в графе есть цикл отрицательного веса, алгоритм Флойда может не найти кратчайший путь.  

• Алгоритм Флойда ищет кратчайшие пути только в графах без циклов отрицательного веса.  

• Алгоритм Дейкстры работает за O(V^2), но ищет расстояние от одной вершины до всех остальных.  

• Алгоритм Флойда работает за O(V^3), но работает "оптом", от каждой вершины до каждой.  

• Оба алгоритма могут работать с любыми весами ребер, если нет отрицательных циклов.