Ю. Беляева (АУ)
Поиск кратчайших путей в дорожной сети

В докладе будет рассказано об алгоритмах поиска кратчайшего пути в дорожных сетях. Широко известный алгоритм Дейкстры оказывается слишком медленным для поиска путей на больших дорожных сетях, таких, как дорожная сеть США или Европы. Алгоритмы с предобработкой в данном случае работают гораздо лучше: на первой стадии по карте подсчитывается вспомогательная информация, которая далее помогает быстро выполнять запросы. В лекции будут рассмотрены несколько вариантов подобных алгоритмов.

Доклад основан на лекциях, прочитанных Ренато Вернеком в рамках летней школы Microsoft Data Structures and Algorithms School (MIDAS) 2010 (http://logic.pdmi.ras.ru/midas).