Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

An Efficient Point-to–Point Shortest Path Algorithm
Алгоритмы на графах

Что: Лекция
Когда: Воскресенье, 01 июня 2008, 13:00–15:00
Слайды: graphalgorithms_lecture_010608.pdf


We study the point-to–point shortest path problem in a setting where preprocessing is allowed. The two main techniques we address are ALT and REACH. ALT is A* search with lower bounds based on landmark distances and triangle inequality. The REACH approach precomputes locality values on vertices and uses them to prune the search. We improve on REACH in several ways. In particular, we add shortcut arcs which reduce vertex reaches. Our modifications greatly reduce both preprocessing and query times. Our algorithm combines in a natural with ALT, yielding significantly better query times and allowing a wide range of time–space trade–offs. The resulting algorithms are quite practical for our motivating application, computing driving directions, both for server and for portable device applications. The ideas behind our algorithms are elegant and may have other applications as well.