Алгоритм Дейкстры — это алгоритм на графах, находящий кратчайшие пути от одной вершины до всех остальных вершин взвешенного ориентированного или неориентированного графа с неотрицательными весами рёбер.
Основные шаги алгоритма:
- Инициализация: Устанавливаем расстояние до начальной вершины 0, до всех остальных — бесконечность. Создаем набор непосещенных вершин.
- Выбор вершины: Выбираем из непосещенных вершин ту, у которой текущее минимальное расстояние.
- Обновление расстояний: Для каждого соседа выбранной вершины, если путь через текущую вершину короче текущего расстояния до этого соседа, обновляем расстояние.
- Помещение в посещенные: Перемещаем выбранную вершину из набора непосещенных в набор посещенных.
- Повторение: Повторяем шаги 2-4, пока все вершины не будут посещены или пока набор непосещенных вершин не станет пустым.
Используется в следующих случаях:
- Нахождение кратчайшего пути: В навигационных системах (GPS), сетевых протоколах (например, OSPF) для определения оптимального маршрута.
- Сетевое маршрутизация: Для определения наиболее эффективных путей передачи данных в компьютерных сетях.
- Планирование производства: Для оптимизации последовательности операций с минимальными затратами времени или ресурсов.
- Обработка изображений: В некоторых алгоритмах для поиска оптимальных траекторий или сегментации.
- Игры: Для поиска кратчайшего пути персонажа или объектов по игровому полю.
Пример псевдокода:
plaintext