Алгоритм Дейкстры находит кратчайшие пути от одной начальной вершины до всех остальных вершин во взвешенном ориентированном или неориентированном графе с неотрицательными весами ребер.
Принцип работы:
- Инициализация: Присваивает начальной вершине расстояние 0, а всем остальным — бесконечность. Все вершины, кроме начальной, помечаются как непосещенные.
- Итерация: Пока есть непосещенные вершины:
- Выбирает непосещенную вершину с наименьшим текущим расстоянием.
- Помечает ее как посещенную.
- Для всех ее соседей, если путь через текущую вершину короче текущего кратчайшего пути до соседа, обновляет расстояние до соседа.
Структуры данных:
- Часто используются приоритетная очередь (например, на основе кучи) для эффективного выбора вершины с минимальным расстоянием.
- Массив или словарь для хранения текущих кратчайших расстояний.
Ограничения:
- Работает только с неотрицательными весами ребер.
python