Ученые Казанского национального исследовательского технического университета им. А. Н. Туполева (КНИТУ-КАИ) определили, что алгоритм Дейкстры является самым точным и эффективным методом расчета транспортных маршрутов. Он выполняет вычисления быстрее других алгоритмов и исключает ошибки за счет однократного прохождения каждой точки маршрута.
Исследователи сравнили три популярных алгоритма: Дейкстры, Флойда и Беллмана. Первый действует по принципу навигатора, строя маршрут от одной точки ко всем возможным направлениям. Алгоритм Флойда анализирует все возможные пути между любыми точками на карте, а Беллман планирует маршрут пошагово, что делает его менее эффективным.
"Алгоритм Дейкстры оказался оптимальным по совокупности характеристик – он и быстрый, и надежный, исключая ошибки при расчете маршрутов."
— Ильдус Ризаев, кандидат технических наук, доцент КНИТУ-КАИ
Тестирование показало, что алгоритм Дейкстры выполняет расчеты за 0,969 секунды, тогда как его конкуренты требуют больше времени. Ключевым преимуществом метода является работа только с положительными значениями расстояний, что соответствует реальным условиям и предотвращает зацикливание.
Практическое применение разработки особенно актуально для логистических компаний, служб доставки и городского планирования. Использование геоинформационных систем в сочетании с этим алгоритмом позволит автоматизировать процесс расчета маршрутов, ускоряя логистические операции и снижая риск ошибок.
Источник: пресс-служба Казанского национального исследовательского технического университета им. А. Н. Туполева (КНИТУ-КАИ)
