Учёные из Казани показали наиболее эффективный алгоритм для транспортных маршрутов

Исследования специалистов Казанского национального исследовательского технического университета им. А. Н. Туполева (КНИТУ-КАИ) показали, что для расчета транспортных маршрутов оптимален алгоритм Дейкстры.

Сравнительный анализ различных математических методов показал, что данный алгоритм не только более быстрый, но и исключает ошибки при расчетах, благодаря однократному прохождению каждой точки маршрута.

Ученые провели анализ трех популярных алгоритмов поиска кратчайших путей. В ходе тестирования на реальных данных маршрутов, алгоритм Дейкстры показал явное преимущество, выполняя расчет за 0,969 секунды, в то время как Флойд и Беллман затратят 1,029 и 1,004 секунды соответственно.

Для логистических компаний это означает возможность быстро прокладывать оптимальные маршруты между городами, учитывая все возможные пути, включая морские порты и железнодорожные узлы. Например, при расчете маршрута доставки из Шанхая в Казань система за несколько секунд предложит оптимальный путь, что значительно экономит время, исключая необходимость ручного анализа карт.

Как отметил Ильдус Ризаев, кандидат технических наук и доцент кафедры автоматизированных систем обработки информации и управления КНИТУ-КАИ, при выборе алгоритма важна не только скорость, но и предотвращение ошибок, таких как зацикливание на участках пути. Метод Дейкстры идеально сочетает эти качества — быстроту и надежность.