Что такое алгоритм Дейкстры?

Алгоритм Дейкстры — это алгоритм поиска кратчайшего пути от одной начальной вершины до всех других вершин в взвешенном ориентированном или неориентированном графе с неотрицательными весами рёбер.

Основные принципы:

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

Шаги алгоритма:

1. Инициализировать расстояния до всех вершин как бесконечность, кроме начальной вершины, расстояние до которой равно 0.
2. Создать набор вершин, которые еще не были обработаны.
3. Повторять, пока есть необработанные вершины: а. Выбрать необработанную вершину u с минимальным расстоянием. б. Пометить u как обработанную. в. Для каждой смежной вершины v вершины u: i. Если расстояние до v больше, чем расстояние до u плюс вес ребра u->v, обновить расстояние до v.

Пример реализации (псевдокод):

python