08.03.301 Алгоритм Дейкстры - justjune/AiSD2026 GitHub Wiki

Определения

Алгоритм Дейкстры является предпочтительным методом поиска кратчайших путей в графах со взвешенными ребрами и/или вершинами. Алгоритм находит кратчайший путь от заданной начальной вершины S ко всем другим вершинам графа, включая требуемую конечную вершину T. [Скиена 2022 с. 301]

предпочтительный метод - скорее всего, автор имеет в виду хороший алгоритм.(Уточнение автора заметки.)

Граф - это абстратное понятие, посредством которого можно описывать разнообразные реальные явления. Граф G = (V, E), состоит из набора вершин V и набора ребер E, соединяющих пары вершин. [Скиена 2022 с. 234]

Граф со взешенными ребрами/вершинами(взвешенный граф) - это граф, каждому ребру/вершине которого присвоено некоторое вещественное число, называемое весом ребра/вершины. Иными словами, на множестве ребер/вершин задана функция W:V→R / Y:E→R. [Algocode wiki]

Путь(в графах) - это последовательность ребер, соединяющих две вершины. [Скиена 2022 с. 299]

Кратчайший путь(в графах) - путь который минимизирует сумму весов ребер во взвешенном графе или имеет наименьшее число ребер в невзвешенном графе. [Скинена 2022 с. 299]

Работа алгоритма

Инициализация. Будем присваивать каждой вершине "расстояние" и изменять его, если нашли более оптимальный путь. Выбираем стартовую вершину, расстояние до самой себя у этой вершины равно нулю. Про остальные мы пока не знаем, поэтому обозначим их расстояние как бесконечность.

Ход алгоритма. Выбираем не рассмотренную вершину с минимальным значением, помечаем ее w. Смотрим все пути из неё до других вершин, и сравниваем с значениями при вершинах. Если значение w + цена перехода до вершины меньше ее значения, то меняем значение на новое. Отмечаем вершину w как рассмотренную.

Конец алгоритма. Когда не рассмотренные вершины заканчиваются, алгоритм прекращает работу. Результат его действия — список кратчайших расстояний до каждой точки из исходной.

Пример работы алгоритма

результатом будет нахождение "расстояний" от стартовой вершины, до всех остальных.

Примечание

Если мы ищем кратчайший путь от точки 1 до точки 2, то алгоритм начинает своё действие с точки 1 и заканчивается когда точка 2 становится рассмотренной.

Так же можно дополнительно записывать массив предков, чтобы восстановить кратчайший путь по вершинам. Массив Parent в момент инициализации выглядит так: [-1, -1, -1, ..., -1] (-1 означает, что предки еще не определены) Каждый раз, когда мы находим более оптимальный путь для вершины y, мы перезаписываем ее "расстояние" dist[y] = new, а так же записываем предка Parent[y] = w.