Finding shortest paths in large scale networks

Abstract

Finding the shortest path between two points in a network is a fundamental problem in computer science with many applications. By exploiting properties of the underlying networks we improve and extend one of the state-of-the-art algorithms for finding shortest paths in road networks, Transit Node Routing (TNR). We develop a new algorithm for finding shortest pathsin public multi-modal transport networks, where we need to deal with other requirements such as transfers, multi-objectiveness, user preferences, etc. Finally we extend our technique to the new domain of grid networks, where one of the challenges is to deal with path symmetries.