Алгоритм Дейкстры - это классический алгоритм на графах, который находит кратчайшие пути от одной заданной вершины (источника) до всех остальных вершин в графе

Проще говоря, это цифровой аналог поиска самого быстрого маршрута на карте от вашего дома до любой другой точки в городе.

Главная фишка (жадный выбор)

Алгоритм работает по «жадному» принципу: на каждом шаге он выбирает ту вершину, до которой на данный момент известен самый короткий путь, фиксирует его как окончательный, а затем проверяет, нельзя ли через эту новую вершину быстрее добраться до её соседей (этот процесс называется релаксацией рёбер).

Как он работает (на пальцах)

1. Вы стоите в начальной точке. Расстояние до неё равно 0, до всех остальных точек - бесконечность ? (мы их ещё не знаем).

2. Вы смотрите на всех соседей текущей точки и считаете расстояние до них. Если новый путь короче того, что был записан раньше, обновляете значение.

3. Отмечаете текущую точку как «посещённую» - сюда мы уже нашли самый короткий маршрут.

4. Выбираете среди непосещённых точек ту, до которой сейчас получилось самое маленькое расстояние, перемещаетесь в неё и повторяете шаг 2.

5. Алгоритм завершается, когда все доступные точки будут посещены.

Важное ограничение

• Алгоритм Дейкстры корректно работает только графах с неотрицательными весами рёбер.

• Если в графе есть дороги с «отрицательным весом» (например, за проезд по участку вам доплачивают, а не вы платите), алгоритм уйдёт в ступор или выдаст неверный результат. Для таких задач используют алгоритм Беллмана-Форда.

Где применяется?

• Навигаторы и карты (Google Maps, Яндекс.Карты) - поиск кратчайшего автомобильного маршрута.

• Сетевая маршрутизация - протокол OSPF (Open Shortest Path First) использует этот алгоритм для поиска кратчайшего пути передачи пакетов данных в компьютерных сетях.

• Игры - поиск путей для юнитов или персонажей на карте.

Телеграм: t.me/ainewsline

Источник: vk.com

Комментарии: