The Shortest Path Problem

• Студент: Алексей Гуревич
• Руководитель: Валерий Лесин

Описание: Целью проекта является создание приложения, решающего задачу поиска кратчайшего пути между двумя точками на карте дорог. В приложении должны быть реализованы как классические алгоритмы Дейкстры и A-star, так и их наиболее современные быстрые модификации.

Положение на начало весеннего семестра:

• разработана графическая оболочка для тестирования алгоритмов,
• реализованы следующие алгоритмы:

- алгоритм Дейкстры,

- a-star.

• а также их оптимизации на основе:

- использования двунаправленного поиска,

- якорных точек (landmark) - ALT,

- подсчета достижимости (reach) - REAL.

Предполагаемые этапы:

• ускорение алгоритма подсчета достижимости (использование механизма shortcut, распараллеливание вычилений),
• исследование и реализация алгоритмов "contraction hierarchies" (начало апреля),
• исследование и реализация алгоритмов "transit node routing" (начало мая),
• <возможный этап> слияние с проектом Евгения Баталова (АУ, кафедра SE, 5 курс) с целью создание многопользовательского приложения с web-интерфейсом для поиска кратчайших путей на графе дорог на основе разработанных алгоритмов. (конец мая)

Ожидаемый результат:

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