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