Speed Up Techniques for Shortest Path Computations Dorothea Wagner and Thomas Willhalm Universita t Karlsruhe TH Fakulta t fu r Informatik Institut fu r Theoretische Informatik D 76128 Karlsruhe wagner willhalm ira uka de http i11www informatik uni karlsruhe de Abstract During the last years several speed up techniques for Dijkstra s algorithm have been published that maintain the correctness of the algorithm but reduce its running time for typical instances They are usually based on a preprocessing that annotates the graph with additional information which can be used to prune or guide the search Timetable information in public transport is a traditional application domain for such techniques In this paper we provide a condensed overview of new developments and extensions of classic results Furthermore we discuss how combinations of speed up techniques can be realized to take advantage from di erent strategies 1 Introduction Computing shortest paths is a base operation for many problems in tra c applications The most prominent are certainly route planning systems for cars bikes and hikers or timetable information systems for scheduled vehicles like trains and busses If such a system is realized as a central server it has to answer a huge number of customer queries asking for their best itineraries Users of such a system continuously enter their requests for nding their best connections Furthermore similar queries appear as sub problems in line planning timetable generation tour planning logistics and tra c simulations The algorithmic core problem that underlies the above scenario is a special case of the single source shortest path problem on a given directed graph with non negative edge lengths While this is obvious for route planning in street networks di erent models and approaches have been presented to solve timetable information by nding shortest paths in an appropriately de ned graph The typical problem to be solved in timetable information is given a departure and an arrival station as well as a departure time which is the connection that arrives as early as possible at the arrival station There are two main approaches for Partially supported by the Future and Emerging Technologies Unit of EC IST priority 6th FP under contract no FP6 021235 2 project ARRIVAL W Thomas and P Weil Eds STACS 2007 LNCS 4393 pp 23 36 2007 c Springer Verlag Berlin Heidelberg 2007 24 D Wagner and T Willhalm modeling timetable information as shortest path problem the time expanded and the time dependent approach For an overview of models and algorithms for optimally solving timetable information we refer to 28 In any case the particular graphs considered are huge especially if the model used for timetable information expands time by modelling each event by a single vertex in the graph Moreover the number of queries to be processed within very short time is huge as well This motivates the use of speed up techniques for shortest path computations The main focus is to reduce the response time for on line queries In this sense a speed up technique is considered as a technique to reduce the search space of Dijkstra s algorithm e g by using precomputed information or inherent information contained in the data Actually often the underlying data contain geographic information that is a layout of the graph is provided Furthermore in many applications the graph can be assumed to be static which allows a preprocessing Due to the size of the graphs considered in route planning or timetable information and the fact that those graphs are typically sparse preprocessing space requirements are only acceptable to be linear in the number of nodes In this paper we provide a systematic classi cation of common speed up techniques and combinations of those Our main intention is to give a concise overview of the current state of research We restrict our attention to speed up techniques where the correctness of the algorithms is guaranteed i e that provably return a shortest path However most of them are heuristic with respect to the running time More precisely in the worst case the algorithm with speed up technique can be slower than the algorithm without speed up technique But experimental studies showed sometimes impressive improvements concerning the search front and consequently the running time For most of these techniques experimental results for di erent real world graphs as well as generated graphs have been reported However as the e ectiveness of certain speed up techniques strongly depends on the graph data considered we do not give a comparison of the speed ups obtained But we want to refer to the 9th DIMACS Implementation Challenge Shortest Paths where also experiments on common data sets were presented 7 In the next section we will provide some formal de nitions and a description of Dijkstra s algorithm Section 3 presents a classi cation of speed up techniques for Dijkstra s algorithm and discusses how they can be combined 2 2 1 Preliminaries De nitions A directed graph G is a pair V E where V is a nite set of nodes and E is a set of edges where an edge is an ordered pair u v of nodes u v V Throughout this paper the number of nodes V is denoted by n and the number of edges E is denoted by m For a node u V the number of outgoing edges u v E is called the degree of the node A path in G is a sequence of nodes u1 uk such that ui ui 1 E for all 1 i k A path with u1 uk is called a cycle Speed Up Techniques for Shortest Path Computations 25 1 for all nodes u V set dist u 2 initialize priority queue Q with source s and set dist s 0 3 while priority queue Q is not empty 4 get node u with smallest tentative distance dist u in Q 5 for all neighbor nodes v of u 7 set new dist dist u w u v 8 if new dist dist v 9 if dist v 10 insert neighbor node v in Q with priority new dist 11 else 12 set priority of neighbor node v in Q to new dist 13 set dist v new dist Algorithm 1 Dijkstra s algorithm Given edge weights l E R lengths the length of a path P u1 uk is the sum of the lengths of its edges l P 1 i k l ui ui 1 For two nodes s t V a shortest s t path is a path of minimal length with u1 s and uk t The graph theoretic distance d s t of s and t is the length of a shortest s t path A layout of a graph G V E is a function L V R2 that assigns each node a position in R2 The Euclidean distance between two nodes u v V is then denoted by L u L v A graph without multiple edges can have up to O n2 edges We call a graph sparse if m O
View Full Document
Unlocking...