Задача Задача №3715671
А
А
Реши задание на изображении
Краткий ответ
| Критерий | Алгоритм Дейкстры | Алгоритм Флойда—Уоршелла |
|---|---|---|
| Решаемая задача | Находит кратчайшие пути от одной заданной вершины ко всем остальным | Находит кратчайшие пути между всеми парами вершин графа |
| Подход к решению | Жадный алгоритм | Динамическое программирование |
| Структура данных | Использует список смежности или матрицу смежности | Оперирует матрицей смежности и хранит результаты в матрице расстояний |
| Требования к графу | Работает только с неотрицательными весами рёбер | Допускает отрицательные веса рёбер |
Почему так
- Дейкстра начинает с одной вершины и каждый раз выбирает ближайшую ещё не обработанную вершину. Поэтому это жадный алгоритм.
- Флойд—Уоршелл сразу рассматривает расстояния между всеми парами вершин и постепенно улучшает их, разрешая использовать новые промежуточные вершины. Это динамическое программирование.
- Дейкстра не работает с отрицательными рёбрами: уже выбранное кратчайшее расстояние может впоследствии уменьшиться.
- Флойд—Уоршелл допускает отрицательные рёбра, но в графе не должно быть отрицательных циклов.
Проверка: все 8 карточек распределяются по две в каждом из четырёх разделов.
