- Алгоритм Флойда – Уоршалла – это классический алгоритм нахождения кратчайших путей между всеми парами вершин. Его реализация на C++ предельно лаконична и основана на тройном вложенном цикле и принципах динамического программирования. Алгоритм эффективен для графов небольшого размера (до нескольких сотен вершин) из-за кубической сложности.
- Назначение: нахождение кратчайших путей между всеми парами вершин во взвешенном графе.
- Алгоритм работает с ориентированными и неориентированными графами.
- Алгоритм может работать с отрицательными весами (но не с отрицательными циклами).
- Сложность: O (V3), где V – количество вершин.
- Алгоритм последовательно улучшает оценку кратчайшего пути, проверяя, можно ли добраться из вершины i в вершину j через промежуточную вершину k быстрее, чем напрямую. «Напрямую» означает текущий известный путь из вершины i в вершину j без использования промежуточных вершин.
- Основная формула (рекуррентное соотношение): dist [i][j] = min (dist [i][j], dist [i][k] + dist [k][j]). На каждом шаге k мы проверяем, является ли путь через вершину k короче текущего известного пути из i в j.
Информатика • 11 класс
4
Алгоритм Флойда – Уоршалла (C++)
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках