🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Алгоритм Дейкстры - это классический алгоритм на графах, который находит кратчайшие пути от одной заданной вершины (источника) до всех остальных вершин в графе.
Проще говоря, это цифровой аналог поиска самого быстрого маршрута на карте от вашего дома до любой другой точки в городе.
🔑 Главная фишка (жадный выбор)
Алгоритм работает по «жадному» принципу: на каждом шаге он выбирает ту вершину, до которой на данный момент известен самый короткий путь, фиксирует его как окончательный, а затем проверяет, нельзя ли через эту новую вершину быстрее добраться до её соседей (этот процесс называется релаксацией рёбер).
⚙️ Как он работает (на пальцах)
1. Вы стоите в начальной точке. Расстояние до неё равно 0, до всех остальных точек - бесконечность ∞ (мы их ещё не знаем).
2. Вы смотрите на всех соседей текущей точки и считаете расстояние до них. Если новый путь короче того, что был записан раньше, обновляете значение.
3. Отмечаете текущую точку как «посещённую» - сюда мы уже нашли самый короткий маршрут.
4. Выбираете среди непосещённых точек ту, до которой сейчас получилось самое маленькое расстояние, перемещаетесь в неё и повторяете шаг 2.
5. Алгоритм завершается, когда все доступные точки будут посещены.
⚠️ Важное ограничение
• Алгоритм Дейкстры корректно работает только графах с неотрицательными весами рёбер.
• Если в графе есть дороги с «отрицательным весом» (например, за проезд по участку вам доплачивают, а не вы платите), алгоритм уйдёт в ступор или выдаст неверный результат. Для таких задач используют алгоритм Беллмана-Форда.
🛠 Где применяется?
• Навигаторы и карты (Google Maps, Яндекс.Карты) - поиск кратчайшего автомобильного маршрута.
• Сетевая маршрутизация - протокол OSPF (Open Shortest Path First) использует этот алгоритм для поиска кратчайшего пути передачи пакетов данных в компьютерных сетях.
• Игры - поиск путей для юнитов или персонажей на карте.
♻️ Сделай репост, чтобы помочь другим.
📲 Мы в MAX
👉 @Bookflow