IntroductionPreliminariesDefinitionsShortest Path ProblemSpeed-Up TechniquesBidirectional SearchGoal-Directed Search or A*Hierarchical MethodsNode and Edge LabelsCombining Speed-Up TechniquesConclusionSpeed-Up Techniques for Shortest-PathComputationsDorothea Wagner and Thomas WillhalmUniversit¨at Karlsruhe (TH)Fakult¨at f¨ur InformatikInstitut f¨ur Theoretische InformatikD-76128 Karlsruhe{wagner,willhalm}@ira.uka.dehttp://i11www.informatik.uni-karlsruhe.de/Abstract. During the last years, several speed-up techniques for Dijk-stra’s algorithm have been published that maintain the correctnessof the algorithm but reduce its running time for typical instances. Theyare usually based on a preprocessing that annotates the graph with ad-ditional information which can be used to prune or guide the search.Timetable information in public transport is a traditional application do-main for such techniques. In this paper, we provide a condensed overviewof new developments and extensions of classic results. Furthermore, wediscuss how combinations of speed-up techniques can be realized to takeadvantage from different strategies.1 IntroductionComputing shortest paths is a base operation for many problems in traffic appli-cations. The most prominent are certainly route planning systems for cars, bikesand hikers, or timetable information systems for scheduled vehicles like trainsand busses. If such a system is realized as a central server, it has to answer ahuge number of customer queries asking for their best itineraries. Users of sucha system continuously enter their requests for finding their “best” connections.Furthermore, similar queries appear as sub-problems in line planning, timetablegeneration, tour planning, logistics, and traffic simulations.The algorithmic core problem that underlies the above scenario is a specialcase of the single-source shortest-path problem on a given directed graph withnon-negative edge lengths. While this is obvious for route planning in streetnetworks, different models and approaches have been presented to solve timetableinformation by finding shortest paths in an appropriately defined graph. Thetypical problem to be solved in timetable information is “given a departure andan arrival station as well as a departure time, which is the connection that arrivesas early as possible at the arrival station?”. There are two main approaches forPartially supported by the Future and Emerging Technologies Unit of EC (ISTpriority 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 200724 D. Wagner and T. Willhalmmodeling timetable information as shortest path problem, the time-expandedand the time-dependent approach. For an overview of models and algorithms foroptimally solving timetable information we refer to [28].In any case the particular graphs considered are huge, especially if the modelused for timetable information expands time by modelling each event by a singlevertex in the graph. Moreover, the number of queries to be processed withinvery short time is huge as well. This motivates the use of speed-up techniquesfor shortest-path computations. The main focus is to reduce the response time foron-line queries. In this sense, a speed-up technique is considered as a techniqueto reduce the search space of Dijkstra’s algorithm e.g. by using precomputedinformation or inherent information contained in the data. Actually, often theunderlying data contain geographic information, that is a layout of the graph isprovided. Furthermore, in many applications the graph can be assumed to bestatic, which allows a preprocessing. Due to the size of the graphs consideredin route planning or timetable information and the fact that those graphs aretypically sparse, preprocessing space requirements are only acceptable to belinear in the number of nodes.In this paper, we provide a systematic classification of common speed-uptechniques and combinations of those. Our main intention is to give a conciseoverview of the current state of research. We restrict our attention to speed-uptechniques where the correctness of the algorithms is guaranteed, i.e., that prov-ably return a shortest path. However, most of them are heuristic with respect tothe running time. More precisely, in the worst case, the algorithm with speed-uptechnique can be slower than the algorithm without speed-up technique. But ex-perimental studies showed–sometimes impressive–improvements concerning thesearch front and consequently the running time. For most of these techniques,experimental results for different real-world graphs as well as generated graphshave been reported. However, as the effectiveness of certain speed-up techniquesstrongly depends on the graph data considered, we do not give a comparison ofthe speed-ups obtained. But we want to refer to the 9th DIMACS Implementa-tion Challenge - Shortest Paths where also experiments on common data setswere presented [7].In the next section, we will provide some formal definitions and a descriptionof Dijkstra’s algorithm. Section 3 presents a classification of speed-up tech-niques for Dijkstra’s algorithm and discusses how they can be combined.2 Preliminaries2.1 DefinitionsA (directed) graph G is a pair (V,E), where V is a finite set of nodes and E is a setof edges, where an edge is an ordered pair (u, v)ofnodesu, v ∈ V . Throughoutthis paper, the number of nodes |V | is denoted by n and the number of edges |E|is denoted by m.Foranodeu ∈ 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= ukis called a cycle.Speed-Up Techniques for Shortest-Path Computations 251 for all nodes u ∈ V set dist(u):=∞2 initialize priority queue Q with source s and set dist(s):=03 while priority queue Q is not empty4 get node u with smallest tentative distance dist(u)inQ5 for all neighbor nodes v of u7setnew-dist := dist(u)+w(u, v)8ifnew-dist < dist(v)9ifdist(v)=∞10 insert neighbor node v in Q with priority new-dist11 else12 set priority of neighbor node v in Q to new-dist13 set dist(v):=new-distAlgorithm 1. Dijkstra’s algorithmGiven 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<kl(ui,ui+1). For two nodess, t ∈
View Full Document
Unlocking...