Алгоритм Дейкстры — это алгоритм поиска кратчайшего пути от одной начальной вершины до всех других вершин в взвешенном ориентированном или неориентированном графе с неотрицательными весами рёбер.
Основные принципы:
- Алгоритм работает в пошаговом режиме.
- На каждом шаге выбирается еще не обработанная вершина с минимальным текущим расстоянием от начальной.
- Расстояния до смежных вершин обновляются, если найден более короткий путь через текущую вершину.
Шаги алгоритма:
- Инициализировать расстояния до всех вершин как бесконечность, кроме начальной вершины, расстояние до которой равно 0.
- Создать набор вершин, которые еще не были обработаны.
- Повторять, пока есть необработанные вершины:
а. Выбрать необработанную вершину
u с минимальным расстоянием.
б. Пометить u как обработанную.
в. Для каждой смежной вершины v вершины u:
i. Если расстояние до v больше, чем расстояние до u плюс вес ребра u->v, обновить расстояние до v.
Пример реализации (псевдокод):
python
Сложность алгоритма:
- Используя списки и линейный поиск минимального расстояния: O(V^2), где V - количество вершин.
- Используя очередь с приоритетом (например, бинарную кучу): O((V + E) log V), где E - количество рёбер.
Применение:
- Поиск кратчайших маршрутов на картах (GPS-навигаторы).
- Маршрутизация в компьютерных сетях.
- Поиск кратчайших путей в графах зависимостей.