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