Алгоритмы поиска кратчайших путей (Дейкстра, Флойд): ЕГЭ по информатике

Тема посвящена алгоритмам поиска кратчайших путей в графах: алгоритму Дейкстры (для неотрицательных весов) и алгоритму Флойда (для всех пар вершин). На ЕГЭ по информатике эти алгоритмы встречаются в заданиях на анализ графов, таблиц смежности и весов, а также при программировании. Необходимо…

Что нужно знать

Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных во взвешенном графе без отрицательных весов.
Алгоритм Флойда (Флойда-Уоршелла) находит кратчайшие пути между всеми парами вершин, может работать с отрицательными весами (но без отрицательных циклов).
В ЕГЭ часто встречаются задания на нахождение кратчайшего пути между двумя вершинами по таблице смежности или схеме дорог.
Для ручного решения удобно использовать метод Дейкстры с заполнением таблицы расстояний.
Алгоритм Флойда реализуется тройным циклом по промежуточным вершинам.
Сложность алгоритма Дейкстры: O(N^2) при простой реализации, O((N+M) log N) с приоритетной очередью.

Термины и понятия

Граф: совокупность вершин и соединяющих их рёбер (дуг).
Взвешенный граф: граф, каждому ребру которого сопоставлено число (вес), например, расстояние или стоимость.
Кратчайший путь: путь между двумя вершинами с минимальной суммой весов рёбер.
Алгоритм Дейкстры: алгоритм поиска кратчайших путей от одной вершины до всех остальных, работающий при неотрицательных весах рёбер.
Алгоритм Флойда: алгоритм поиска кратчайших путей между всеми парами вершин, основанный на динамическом программировании.
Матрица смежности: таблица N×N, где элемент (i,j) равен весу ребра из i в j (или бесконечности, если ребра нет).
Релаксация: операция обновления текущего кратчайшего расстояния до вершины при обнаружении более короткого пути.

Частые ошибки

Применение алгоритма Дейкстры для графов с отрицательными весами (что приводит к неверному результату).
Ошибки в ручных вычислениях: забывают обновлять расстояния при релаксации, путают порядок вершин.
Неверное заполнение матрицы смежности: не учитывают отсутствие ребра (бесконечность) или симметричность для неориентированного графа.
В алгоритме Флойда неправильный порядок циклов (промежуточная вершина должна быть во внешнем цикле).

Как пройти тему

В курсе «Информатика» тема «Алгоритмы поиска кратчайших путей (Дейкстра, Флойд)» занимает 2 занятия по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Графы. Алгоритмы обхода графа (BFS, DFS)
Следующая тема: Алгоритмы сортировки и их сложность

Все темы: ЕГЭ по информатике