Друзья!

В этот вторник (18.11.25) на научном семинаре выступит Левон Минасян.
Прилагаем анонс его доклада:

Сверхбыстрый поиск кратчайшего пути в графах дорог: Contraction Hierarchies, Transit Node Routing

На докладе мы обсудим все современные подходы поиска кратчайших путей в графе.
Сначала мы сфокусируемся на непосредственном ускорении алгоритма Дейкстры, посмотрим на множество
существующих на данных момент эвристик: A*, ALT, Arc Flags, Reach, Reach Flags, REAL.
Во второй части мы детально обсудим рок-звезду в поиске кратчайших путей: алгоритм Contraction Hierarchies. Закончим обзором SOTA-подхода: спайки Contraction Hierarchies с фреймворком Transit Node Routing.

Доклад будет доступен любому слушателю, хотя бы как-то знакомому с алгоритмом Дейкстры.
Если вы не знаете, как искать кратчайший путь в графе быстрее двустороннего алгоритма Дейкстры(а тем более, если вы не знали, что у алгоритма Дейкстры есть двусторонняя версия), можете считать, что посещение этого доклада вам назначил врач!

Ждем вас 18.10.25 в 18 10 в аудитории 108.

#лаборатория_сложных_сетей