Задача Задача №3715673
А
А
Реши задание на изображении
Краткий ответ: скорее всего, ошибка в строке «Структура данных» для алгоритма Дейкстры. Нужно указать, что он использует очередь с приоритетом для выбора вершины с минимальным текущим расстоянием.
| Критерий | Алгоритм Дейкстры | Алгоритм Флойда—Уоршелла |
|---|---|---|
| Решаемая задача | Находит кратчайшие пути от одной заданной вершины ко всем остальным | Находит кратчайшие пути между всеми парами вершин |
| Подход к решению | Жадный алгоритм | Динамическое программирование |
| Структура данных | Использует очередь с приоритетом; граф может храниться списком или матрицей смежности | Использует матрицу смежности и матрицу расстояний |
| Требования к графу | Работает только с неотрицательными весами рёбер | Допускает отрицательные веса рёбер, но не отрицательные циклы |
Почему так:
- Дейкстра каждый раз выбирает ещё не обработанную вершину с наименьшим расстоянием — это жадный выбор. Поэтому ему нужна очередь с приоритетом.
- Флойд—Уоршелл последовательно проверяет, улучшится ли путь через промежуточную вершину: \[ d[i][j]=\min\bigl(d[i][j],\,d[i][k]+d[k][j]\bigr). \] Поэтому он работает с матрицей и использует динамическое программирование.
- Если после работы алгоритма Флойда—Уоршелла для некоторой вершины \(d[i][i]<0\), в графе есть отрицательный цикл, и кратчайший путь для соответствующих вершин не определён.
Проверь в своей таблице прежде всего ячейку Дейкстры в строке «Структура данных»: вместо «список смежности или матрица смежности» выбери вариант про очередь с приоритетом.
Обсуждение
2 сообщения А
Расставь верно карточки
Расставь карточки так:
| Критерий | Алгоритм Дейкстры | Алгоритм Флойда—Уоршелла |
|---|---|---|
| Решаемая задача | Кратчайшие пути от одной вершины до всех остальных | Кратчайшие пути между всеми парами вершин |
| Подход к решению | Жадный алгоритм | Динамическое программирование |
| Структура данных | Очередь с приоритетом | Матрица расстояний |
| Требования к графу | Рёбра должны иметь неотрицательные веса | Допустимы отрицательные рёбра, но не отрицательные циклы |
