Dijkstra’s Algorithm On–Line:
An Empirical Case Study from
Public Railroad Transport1
Frank Schulz
and
Dorothea Wagner
and
Karsten Weihe
University of Konstanz, Department of Computer & Information Science
Traffic information systems are among the most prominent real–world applications of Dijkstra’s
algorithm for shortest paths. We consider the scenario of a central information server in the
realm of public railroad transport on wide–area networks. Such a system has to process a large
number of on–line queries for optimal travel connections in real time. In practice, this problem is
usually solved by heuristic variations of Dijkstra’s algorithm, which do not guarantee an optimal
result. We report results from a pilot study, in which we focused on the travel time as the only
optimization criterion. In this study, various speed–up techniques for Dijkstra’s algorithm were
analysed empirically. This analysis was based on the timetable data of all German trains and on
a “snapshot” of half a million customer queries.2
1. INTRODUCTION
1.1 Problem.
From a theoretical viewpoint, the problem of finding a shortest path from one
node to another one in a graph with edge lengths is satisfactorily solved. In fact,
the Fibonacci–heap implementation of Dijkstra’s algorithm requires O(m+n log n)
time, where n is the number of nodes and m the number of edges [6]. However,
various practical application scenarios impose restrictions that make this sort of
algorithm impractical. For instance, many scenarios impose a strict limitation on
space consumption.3
1 c©ACM, 2000. This is the author’s version of the work. It is posted here by permission of ACM
for your personal use. Not for redistribution. The definitive version was published in Journal of
Experimental Algorithmics, Volume 5(12), 2000, http://www.jea.acm.org
2With special courtesy of the TLC Transport-, Informatik- und Logistik–Consulting GmbH/EVA–
Fahrplanzentrum, a subsidiary of the Deutsche Bahn AG.
3To give a concrete example: if a traffic information system is to be distributed on CD–Rom or to
be run on an embedded system, a naive implementation of Dijkstra’s algorithm would typically
Address: University of Konstanz, Box D188, 78457 Konstanz, Germany
{schulz,wagner}@fmi.uni–konstanz.de, weihek@acm.org
http://www.fmi.uni-konstanz.de/˜{schulz,wagner,weihe}
2
·
F. Schulz and D. Wagner and K. Weihe
In this paper, we consider a different scenario: space consumption is not an issue,
but the system has to answer a potentially infinite number of customer queries for
optimal travel connections on–line. The real–time restrictions are soft, which basi-
cally means that the average response time is more important than the maximum
response time. The concrete scenario we have in mind is a central server for public
railroad transport, which has to process a large number of queries (e.g. a server
that is directly accessible by customers through terminals in the train stations or
through a web interface).
Assumption 1.1. Our computational study is based on two further simplifying
assumptions:
(1) The time tables are identical every day.
(2) The length of a travel connection is exclusively defined as the travel time (to
be specified in greater detail in Definition 1.2 below).
To achieve Assumption 1.1(1), we simply unite the time tables of all days. Due
to this assumption, a customer query need not specify a date.
Definition 1.2. A customer query (or simply query for short) is a triple con-
sisting of two stations, A and B, and an earliest departure time t. Such a query
asks for a connection from A to B that does not start before t and arrives B as
early as possible.
Algorithmic problems of this kind are usually approached heuristically in practice,
which means that an optimal result is not guaranteed.
Definition 1.3. An algorithm for a shortest–path problem is called distance–
preserving if it produces an optimal connection for every input instance.
Distance–preserving algorithms are not in wide use in traffic information sys-
tems, because the average response time of such an algorithm was perceived to be
unacceptable. In a new long–term project, we plan to investigate the question to
what extent distance–preserving variants of Dijkstra’s algorithm have become com-
petitive on contemporary computer technology. Here we give an experience report
from a pilot study, in which we focused on the most fundamental kind of query,
namely the one specified in Definition 1.2 (subject to Assumption 1.1(1)).
This scenario is an example of a general problem in the design of practical algo-
rithms, which we discussed in [22]: computational studies based on artificial (e.g.
random) data do not make much sense, because the characteristics of the real–world
data are crucial for the success or failure of an algorithmic approach in a concrete
use scenario. Hence, experiments on real–world data are the method of choice.
1.2 Related work.
Various textbooks address speed–up techniques for Dijkstra’s algorithm but have
no concrete applications in mind, notably [2] and [14]. In [21], Chapter 4, a brief,
introductory survey of selected techniques is given (with a strong bias towards
the use scenario discussed here). Most work from the scientific side addresses the
single–source variant, where a spanning tree of shortest paths from a designated
exceed the available space.
Dijkstra’s Algorithm On–Line
·
3
root to all other nodes is to be found. Moreover, the main aspect addressed in work
like [5] is the choice of the data structure for the priority queue. In Section 3 below
(paragraph on the “search horizon”), we will see that the scenario considered in
this paper requires algorithmic approaches that are fundamentally different, and
Section 4 will show that the choice of the priority queue is indeed a marginal aspect
in view of the goal of our project.
On the other hand, most application–oriented work in this field is commercial,
not scientific, and there is only a small number of publications. In fact, we are not
aware of any publication especially about algorithms for wide–area railroad traffic
information systems.
Some scientific work has been done on local public transport. For example, [17]
gives some insights into the state of the art. However, local public transport is quite
different from wide–area public transport, because the timetables are very regular,
and the most powerful speed–up techniques are based on the strict periodicity of
the trains, buses, ferries, etc. In contrast, our experience is that the timetables of
the national European train companies are not regular enough to gain a significant
profit from these techniques.4
On the other hand, private transport has been extensively investigated in view of
wide–area networks. Roughly speaking, this means “routing planners” for cars on
city and country maps [9; 1; 4; 20; 12; 18]. This problem is different to ours in that it
is two–dimensional, whereas train timetables induce time as a third dimension: due
to the lack of periodicity, the earliest departure time is significant in our scenario.
In contrast, temporal aspects do not play any role in the work quoted above.5 So
it is not surprising that the research on routing planners has focused on purely
geometric techniques.
Some of the application–oriented work quoted above is based on hierarchical
approaches. This is also one of our strategies (see Section 3.2, strategy “selections of
stations”). For example, in [19] this approach is viewed from a database perspective
without any specific scenario in mind (though with a bias towards road maps).
For completeness, we mention the work on variants of Dijkstra’s algorithm that
are intended to efficiently cope with large data in secondary memory. Chapter 9
of [3] gives an introduction to theoretical and practical aspects. As mentioned above
(“problem” section in the Introduction), the problems caused by the slow access to
secondary memory are beyond the scope of our paper.
Since our main contribution is a computational study, the work on the method-
ology of this sort of study (e.g. [7; 8; 11; 10; 13; 15; 16]) is also related. We will
come back to methodological issues in Section 2.
1.3 Contribution of the paper.
We implemented and evaluated various distance–preserving speed–up techniques for
Dijkstra’s algorithm. The study is based on all train data (winter period 1996/97)
of the Deutsche Bahn AG, the national railroad and train company of Germany.
4This experience is supported by personal communications with people from the industry.
5In principle, temporal aspects would also be relevant for the private transport, for example, the
distinction between “rush hours” and other times of the day. However, this sort of temporal aspect
is quite different from ours and, to our knowledge, not scientifically invesitigated either.
4
·
F. Schulz and D. Wagner and K. Weihe
The processed queries are a “snapshot” of the central Hafas6 server of the Deutsche
Bahn AG, in which all queries of customers of all ticket offices in Germany were
recorded over several hours.
In particular, an input instance consists of a fixed and a variable part:
—Fixed : all input instances include the same set of time tables.
—Variable: the query, that is, departure station, arrival station, and earliest de-
parture time, varies from input instance to input instance.
The result of this snapshot comprises more than half a million queries, which
might suffice for a representative analysis of this particular service (assuming that
the typical query profile of customers does not vary dramatically from day to day).
Due to the above–mentioned insight that the periodicity of the timetables is not
a promising base for algorithmic approaches, the question is particularly interesting
whether geometric techniques like those in routing planners are successful, although
the scenario has geometric and temporal characteristics. We will see that this
question can indeed be answered in the affirmative.
1.4 Overview.
In Section 2 we will discuss the general rationale of our experimental set–up. Then,
in Section 3, we will briefly summarize the algorithmic techniques that we evaluated.
Finally, in Section 4, we will present and discuss the results of the computational
study.
2. EMPIRICAL METHODOLOGY
As mentioned in the Introduction, the question to be answered by our computa-
tional study is very specific:
Are distance–preserving variants of Dijkstra’s algorithm (in the sense
of Definition 1.3) competitive on contemporary computer technology in
the use scenario addressed in this paper?
The notion “competitive” is here used in a very informal sense, which is probably
the sense of interest from an applied viewpoint. Roughly speaking, we regard an
algorithm as competitive if it would probably not become a bottleneck operation in a
typical central server. Such a fuzzy notion does not allow far–reaching conclusions.
We believe that our conclusions (which we will give in detail in Section 4 and
in summary in Section 5) are modest enough to be safely based on our usage of
competitiveness.
The question addressed in our paper is quite different from the questions typically
addressed in methodological work such as [7; 8; 11; 10; 13; 15; 16]. In fact, to
our knowledge, the general focus in the literature is on systematic performance
comparisons of different algorithms without or with only loose relation to concrete
applications. The overwhelming majority of computational studies in theoretical
computer science primarily addresses this kind of question. The method of choice
here is the evaluation of the individual algorithms on artificial (mainly random)
6Hafas is a trademark of the Hacon Ingenieurgesellschaft mbH, Hannover, Germany.
Dijkstra’s Algorithm On–Line
·
5
input data, which is a good base for the systematic variation of parameters, and a
statistical analysis of the computational results.
In contrast, the question we address in this paper is tightly bound to a concrete
application scenario. The profile of the input data is very specific, but a sufficient
specification of this profile in terms of parameters such as the number of nodes/edges
or the average/maximum node degree does not seem to be in our reach.7 Thus,
there is no base for the creation of artificial, yet realistic data. On the other hand,
a snapshot of half a million real customer queries, which is the base of our study,
is certainly sufficient for a profound answer to the above question. Hence, we will
restrict our attention to real–world data.
Note that the question addressed in this paper is binary (yes/no). As mentioned
in the Introduction, the real–time constraints are rather soft. This means that the
overall average response time, taken over the total set of all queries, is the most
important piece of information to decide upon yes or no. However, beyond this
very specific question we also regard an estimation of the scope of the result as
important. For instance, such a large body of response times, if well analysed,
should allow a reliable prediction how the average response time changes if the
average geographic distance of departure and arrival station changes. To give a
concrete example: the percentage of long–distance queries is significantly higher
for the web service than for the ticket office service, from which our snapshot was
taken.
To estimate the effect of variations like this, we will also consider the interdepen-
dence between response times and two parameters, the Euclidean distance between
departure and arrival station and the minimal total travel time computed in re-
sponse to the respective query. In Section 4 we will see that this dependency is
surprisingly strong, which means that we may assume a high level of confidence for
predictions.
As mentioned in the Introduction, we implemented and evaluated various speed–
up techniques for Dijkstra’s algorithm. One notable exception is the bidirected–
search technique. This technique does not really apply in our scenario, because the
target node of the search depends on the arrival time and is thus not known in
advance (see Section 3, paragraph on “bidirected search,” for details). However,
one can imagine a variation of the bidirected–search technique, which does not rely
on the exact arrival time but on an upper bound. To answer the question whether
this class of modified bidirected–search techniques is potentially competitive at all,
we implemented and evaluated an idealized variant, which indeed does rely on the
exact arrival time and thus yields a lower bound on the potential performance of
this class of speed–up techniques.
7Nonetheless, a comparison of the algorithms from Section 3 based on random data and a conven-
tional statistical analysis as advocated by some of the above–mentioned papers may be of interest
in its own right. However, such an analysis does not contribute to our specific question and is
thus beyond the scope of this paper.
6
·
F. Schulz and D. Wagner and K. Weihe
3. ALGORITHMS
3.1 Fundamental Algorithmic Approach
3.1.1 Train graph.. From Assumption 1.1 recall our restriction to time tables
that do not vary from day to day. Due to this restriction, we only need a train
network of 24 hours.
The arrival or departure of a train at a station will be called an event. The
train graph contains one node for every event. Two events v and w are connected
by a directed edge (v, w) if v represents the departure of a train at some station
and w represents the very next arrival of this train at some other station. On the
other hand, two successive events at the same station are connected by an edge (in
positive time direction), which means that every station is represented in the graph
by a cycle through all of its events (the cycle is closed by a turn–around edge at
midnight).
In each case, the length of an edge is the time difference (in minutes) of the
events represented by its endnodes. Obviously, a query then amounts to finding a
shortest path from the earliest event at the departure station not before the earliest
departure time to an arbitrary arrival event at the arrival station.
The data contains 933, 066 events on 6, 961 stations. Consequently, there are
933, 066 · 3/2 = 1, 399, 599 edges in the graph.
3.1.2 Priority queue.. Dijkstra’s algorithm relies on a priority queue, which man-
ages the events on the current “frontier line” of the search. As mentioned above, the
best general worst–case bound, O(m+ n log n), is obtained from Fibonacci heaps,
where n is again the number of events and m the number of edges. We do not use
a Fibonacci heap but a normal heap (also often called a 2–heap), which yields an
O((n +m) log n) bound [6]. Since m ∈ O(n) in train graphs, both bounds reduce
to O(n log n).
As an alternative to heaps, we also implemented the Dial variant as described
in [2]. Basically, this means that the priority queue is realized by an array of buckets
with a cyclically moving array index. The events of the frontier line are distributed
among the buckets, and it is guaranteed that the very next non–empty bucket after
the current array index always contains the candidates to be processed next. The
asymptotic worst–case bound of the Dial implementation of Dijkstra’s algorithm is
O(m+ nL), where L is the largest length of an edge.
3.1.3 Search horizon.. Of course, we deviate from the “textbook version” of Di-
jkstra’s algorithm in that we do not compute the distance of every event from
the source event but terminate the algorithm immediately once the first (and thus
optimal) event at the arrival station is processed. The most fundamental distance–
preserving speed–up technique for our scenario is then a reduction of the search to
a (hopefully) small part of the graph, which contains all relevant events. Figs. 1–
4 demonstrate that such a reduction is crucial. In fact, they reveal that for the
majority of all queries only small fractions of the total area and time horizon are
relevant.
To our knowledge, some commercial implementations remove events and edges
from the graph (more or less heuristically, i.e. losing optimality of distances) before
the search itself takes place. In contrast, we aim at an evaluation of distance–
Dijkstra’s Algorithm On–Line
·
7
0
5000
10000
15000
20000
25000
30000
35000
0
100
200
300
400
500
600
700
800
Fig. 1. The frequency distribution histogram of the queries from the snapshot according to
the Euclidean distance between the departure station and the arrival station (granularity: 15
kilometers).
0
5000
10000
15000
20000
25000
30000
0
100
200
300
400
500
600
700
800
Fig. 2. Like Fig. 1 except that the abscissa now denotes the minimal travel time in minutes
(granularity: 20 minutes).
preserving strategies, so our approach is quite different. First of all, we apply the
amortization technique discussed in [21] to obtain a sublinear expected run time
per query.8 The only obstacle to sublinearity is the initialization of all events with
infinite distance labels in the beginning of the textbook algorithm; in fact, Figs. 1–4
8The term “sublinear expected run time” is here used in a rather informal, experience–oriented
way and not to be understood in a formal probabilistic sense.
8
·
F. Schulz and D. Wagner and K. Weihe
0
5000
10000
15000
20000
25000
0
50
100
150
200
Fig. 3. Like Fig. 1 except that the abscissa now denotes the number of edges in the shortest path
(granularity: 10 edges).
0
50
100
150
200
250
300
350
400
450
500
0
200
400
600
800
1000
1200
Fig. 4. For each minimal travel time (granularity: 20 minutes) the total CPU times of all queries
yielding this value of the travel time are summed up to reveal which range of travel times con-
tributes most of the total CPU time required for all queries.
strongly suggest that on average the main loop of the algorithm only processes a
very small fraction of the graph until the arrival station is seen and the algorithm
terminates.
As described in [21], every event is given an additional time stamp, which stores
the number of the query in which it was reached in the main loop. Whenever
an event is reached, its time stamp is updated accordingly. This update properly
increases the time stamp if and only if this is the first time that the node is seen
Dijkstra’s Algorithm On–Line
·
9
in the current search. This is exactly the situation in which the current distance
label should be infinity. Hence, if the time stamp is increased, the distance label
is regarded as infinite, otherwise the value of the distance label is taken as is.
Consequently, there is no need for an expensive initialization phase, and no event
outside the “search horizon” of the main loop is hit at all.
It might be worth mentioning an equivalent strategy to avoid the initialization
step: An additional data structure, e.g. a linked list, is used to store the nodes
with non-infinite distance labels. Then, all non-infinite distance labels can be reset
to infinity after each query.
3.2 Algorithmic Variations
The good performance of the following additional techniques relies on the general
design decisions introduced in Section 3.1. All of these techniques are independent
of each other in the sense that an arbitrary selection of them may be applied
simultaneously.
3.2.1 Angle restriction.. This technique additionally relies on the coordinates
associated with the individual stations. In a preprocessing step, we apply Dijkstra’s
algorithm to each event to compute shortest paths from this event to all other
stations.9 The results are not stored (this would require too much space) but
only used to compute two values α(v, w) and β(v, w) for each edge (v, w) that
corresponds to a train hop. These 2 ·n/2 values (n again the number of events) are
stored and then used in the on–line system.
More specifically, these values are to be interpreted as angles in the plane. See
Fig. 5. Let (v, w) be an edge from some event v to some other event w, and let
sv and sw be the stations to which events v and w belong, respectively. Then the
values α(v, w) and β(v, w) stored for edge (v, w) span a circle sector with center sv
in the plane, where, say, α(v, w) is the right leg. The values α(v, w) and β(v, w) are
determined such that this circle sector has the following meaning: if the shortest
path from event v to some event u at some station s′ contains (v, w), then s′
has to be in this circle sector. Subject to this condition, the difference of the
angles, (β(v, w)−α(v, w)) mod 2π, is minimum. Clearly, the brute–force application
of Dijkstra’s algorithm in the preprocessing allows one to compute this specific,
narrowest possible circle sector for each edge.
Consequently, edge (v, w) may be ignored by the search if the arrival station is
not in the circle sector of this edge. The restriction of the search to edges whose
circle sectors contain the arrival station is the strategy that we will call “angle
restriction” in the following.
Proposition 3.1. Due to the specific construction of the values α(·, ·) and β(·, ·),
the strategy “angle restriction” is distance–preserving in the sense of Definition 1.3.
3.2.2 Selection of stations.. The basic idea behind this technique is similarly
implemented in various routing planners for the private transport [9; 1; 4; 12].
9This preprocessing takes several hours, which is absolutely acceptable in the practical setting
from which this research originated, namely generating time tables once for every winter/summer
period. Hence, there is no need to optimize the preprocessing.
10
·
F. Schulz and D. Wagner and K. Weihe
( , ) α ( , )
β
s’
u
v w
at
v w
at s
v
1
at s
w
2
Fig. 5. The circle sector spanned by α(v, w) and β(v, w) contains all stations s′ such that there
is an event u at s′ whose shortest path from v starts with (v, w).
0
20000
40000
60000
80000
100000
120000
140000
160000
0
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
Fig. 6. The relation of the number of edges hit without (abscissa) and with (ordinate) strategy
angle selection (granularity: 500 edges).
In general, a certain small set of nodes (i.e. events) is selected, which means
events in our setting. However, we will only select sets of nodes such that either
every node from a station s is selected, or none of the nodes from station s. More
specifically, in the data available to us, every station is assigned an “importance
number,” which is intended to rank its degree of “centrality” in the railroad network.
For our computational study, we select the 225 stations in the highest categories
(see Fig. 10). These stations induce 95, 423 events in total, which constitute our
selection of events.
Let G = (V,E) denote the (directed) train graph. In particular, V is the set of all
events. Moreover, let Ṽ be the set of selected nodes. The strategy is based on what
we will call replaceable paths in the following. Let v, w ∈ V be two events, which
may or may not belong to Ṽ . A path from v to w in G will be called replaceable, if
Dijkstra’s Algorithm On–Line
·
11
no node of the path (except for the endnodes, v and w, themselves) belongs to Ṽ .
Based on this notion, we construct an auxiliary directed graph G′ = (V,E′) on
V . For v, w ∈ V , there is a directed edge (v, w) ∈ E ′ if, and only if, there is a
replaceable path from v to w in G. The length `(v, w) of an edge (v, w) ∈ E ′ in G′
is then defined as the minimum length of a replaceable path from v to w in G.
The auxiliary graph G′ and these edge weights are also constructed once and for
all in a preprocessing step (which only takes a few minutes). Each query is then
answered by the computation of a shortest path in the auxiliary graph G′, and this
path corresponds to a shortest path in the train graph G.
We implement this general approach as follows. First of all, note that it is
not necessary to reconstruct the path in G that corresponds to the shortest path
computed in G′. In fact, what we really want to have from the computation is a
sequence of trains and the stations where to change train. This data can be attached
to the edges of the auxiliary graph in an even more compact (less redundant) and
thus more efficiently evaluable fashion than to the edges of the train graph.
As mentioned above, we select a set of stations, and the events of these stations
are the selected events. Clearly, there is a trade–off. Roughly speaking, the smaller
the number of selected stations is, the larger the resulting connected components
are and, even worse, the larger the number of selected stations neighboring to a
component. Since the number of edges depends on the latter number in a quadratic
fashion, an improvement of performance due to a rigorous reduction of stations is
soon outweighed by the tremendous increase in the number of edges.
It has turned out that in our setting, a minor refinement of this strategy is
sufficient to overcome this trade–off. For this, let u, v, and w be three selected
events such that edges (u, v), (v, w), and (u,w) exist in the auxiliary graph. If
`(u, v)+`(v, w) ≤ `(u,w), then edge (u,w) is dropped in the auxiliary graph. Again,
the optimal distance is preserved. The number of edges grows only moderately after
this modification, so quite a small set of selected stations becomes feasible.
The selected stations induce 95, 423 events in total, which means that the number
of events is approximately reduced by a factor of 10, and the number of stations
is reduced by a factor of 31. This discrepancy between these two factors is not
surprising, because central stations are typically met by more trains than other
stations.
Proposition 3.2. The strategy “selection of stations” is distance–preserving in
the sense of Definition 1.3.
3.2.3 Goal–directed search.. This strategy is based on one real number b(s) for
each station s, which must be a lower bound on the minimal travel time from
s to the arrival station. Let (v, w) ∈ E be an edge, and let sv and sw be the
stations of v and w, respectively. The values b(sv) and b(sw) must additionally
satisfy b(sv)− b(sw) ≤ `(v, w). The length `(v, w) of (v, w) is then replaced by the
modified length `′(v, w) := `(v, w)− b(sv) + b(sw) ≥ 0.
It can be shown that the shortest paths with respect to the length function `′(·, ·)
are identical with the shortest paths with respect to the original length function
`(·, ·). Hence, we may alternately compute a shortest path with respect to `′(·, ·).
The hope is that the “frontier” of the search horizon approaches the arrival station
faster when the modified edge lengths are used. See [14] for a more systematic
12
·
F. Schulz and D. Wagner and K. Weihe
discussion.
Roughly speaking, the tighter the lower bounds s(·) are, the larger the speed–up
effect will be. The base of our lower bounds is the maximum speed of all trains as
a transformation factor. The lower bound for an arbitrary station with respect to a
given target station is the Euclidean distance of these two stations divided by this
factor. These values are computable “on the fly” during the search.
Proposition 3.3. The strategy “goal–directed search” is distance–preserving in
the sense of Definition 1.3.
3.2.4 Bidirected search.. This strategy “merges” two applications of Dijkstra’s
algorithm into one loop. More specifically, one search starts from the source event
and goes forward as usual, whereas the other search starts from the target event
and traverses every edge in backward direction. The algorithm is finished once an
event was labeled permanently by both searches. A shortest path from the source
event to the target event is then easily constructed from the results of the two
searches up to this moment. We refer to [2; 14] for details.
This strategy is not directly applicable in our scenario, because the target event
is not known until the search is finished. Nonetheless, one can imagine variations of
this strategy, in which the backward search indeed starts from the arrival station,
however, not from the optimal arrival time but from an upper bound on this value.
To evaluate the general potential of this strategy in view of our application sce-
nario, we implemented an idealized variant. More specifically, we indeed use the
exact optimal arrival time as a start point for the backward search. Clearly, this
gives a lower bound on the performance of all of these variations of bidirected
search.10 Since we only consider an idealized strategy here, it does not make sense
to evaluate the CPU times achieved by this strategy. Hence, we will restrict the
evaluation of this strategy to operation counts (see Section 4).
3.2.5 Combination of strategies.. In principle, all of these strategies can be freely
combined. In that, the strategy “selection of stations” can be combined with the
strategy “angle restrictions” in two ways, namely the angle restrictions can be
computed for the auxiliary graph, or they can be computed for the train graph and
simply taken over for the auxiliary graph.
4. ANALYSIS OF THE ALGORITHMIC PERFORMANCE
The experiments were performed on a SUN Sparc Enterprise 5000, and the code
was written in C++ using the GNU compiler.
Tables 1 and 2 present a summarizing comparison of all combinations of strate-
gies. Since every node in the train graph has a degree of three, the total number of
algorithmic steps is asymptotically dominated by the number of operations inside
the priority queue. In other words, these operations are representative operation
counts in the sense of [2], Sect. 18. More specifically, for a heap the number of
exchange operations is representative, whereas for the Dial variant the number
of cyclic increments of the moving array index plus the number of the bucket-
operations “insert” and “remove” is representative. The average total number per
10Except for pathological cases that are imagineable but might hardly occur in reality.
Dijkstra’s Algorithm On–Line
·
13
query of these operations are listed in the last part of Tables 1 and 2. As men-
tioned in Section 2, we regard these average numbers as the most important piece
of information in view of our central yes/no question.
For both implementations of the priority queue, the CPU times imply the same
strong ranking of combinations of strategies. Figs. 9–12 might give a visual impres-
sion why this ranking is so unambiguous. Moreover, the discrepancy between the
heap and the Dial implementation in terms of CPU times also decreases roughly
from row to row.
Our experience with several versions of the code is that the exact CPU times are
strongly sensitive to the details of the implementation, but the general tendency
was maintained and seems to be reliable. In particular, the main question raised
in this paper (whether distance–preserving techniques in the sense of Definition 1.3
are competitive) can be safely answered in the affirmative at least for the restriction
of the problem to the total travel time as the only optimization criterion.
However, a detailed look at the results is more insightful (and necessary to con-
clude predictions for scenarios with different profiles as discussed in Section 2).
Fig. 6 shows that there is a very strong correlation between the number of edges
hit with/without strategy “angle restriction.” On the other hand, Fig. 7 shows a
detailed analysis of one particular, exemplary combination of strategies. A com-
parison of the diagrams in Fig. 7 reveals an interesting effect, which is also found
in the analogous diagrams of the other combinations: the CPU times of both the
heap and the Dial implementation “look” linear in the number of nodes hit by the
search.11
This correlation is so strong and the variance is so small that corresponding
diagrams in Fig. 7 look almost identical. Figure 8 reveals the cause.
In other
words, in both cases the operations on the priority queue come close to constant
time on average, even when the average is taken over each query separately.
Finally, the bidirected–search technique required, on average, 5606 nodes, 9497
edges, an operation count of 7531 for the Dial implementation, and an operation
count of 45826 for the heap implementation. As mentioned in the paragraph on
bidirected search in Section 3, it does not make sense to take CPU times here,
because an idealized algorithm was implemented.
Since one can safely assume that the above results for this idealized algorithm
are a lower bound on the real performance of this technique in our scenario, they
give some evidence that bidirected search would be a reasonable choice (assuming
that tight upper bounds on the exact arrival times can be found efficiently), but
might not be the favorite choice.
In Section 2, we raised the question whether the results allow reliable predictions
for similar scenarios such as a web server, where a larger fraction of all queries
asks for long–distance connections. The small variance encourages us to conclude
(with caution) that our results are scalable in an approximately linear fashion to
11From the work on this study we gained the experience that the difference between Θ(n) and
Θ(n log n) may be very small and hidden by the “noise” of the data. Hence, the claim that one
can observe a linear behavior does not really contradict the claim that the asymptotic complexity
is Θ(n logn). In other words, the above claim that the run time be linear is to be taken with a
pinch of salt.
14
·
F. Schulz and D. Wagner and K. Weihe
Selection of stations
Angle restriction
CPU heap
CPU Dial
no
no
0.310
0.103
no
yes
0.036
0.018
yes
no
0.027
0.012
yes
yes (train)
0.007
0.005
yes
yes (auxiliary)
0.005
0.003
Selection of stations
Angle restriction
Nodes
Edges
no
no
17576
31820
no
yes
4744
10026
yes
no
2114
3684
yes
yes (train)
1140
2737
yes
yes (auxiliary)
993
2378
Selection of stations
Angle restriction
Ops. heap
Ops. Dial
no
no
246255
23866
no
yes
24526
3334
yes
no
26304
3660
yes
yes (train)
4973
1197
yes
yes (auxiliary)
3191
932
Table 1. A summary of all computational results for the individual combinations of the techniques
“selection of stations” and “angle restrictions.” The entries “train” and “auxiliary” in column #2
refer to the graph in which the angles were computed (see the last paragraph in Section 3). The
columns #3–#4 give the average over all queries of the snapshot. More specifically, the first table
gives the average raw CPU times, the second table the average number of nodes and edges hit by
the search, and the third table the average operation counts.
scenarios like that.
As announced in the Introduction, the choice of the data structure for the priority
queue seems to be a detail of minor relevance. The difference between the heap and
the Dial implementation looks significant at first glance, however, this seems to be
one of the aspects which are not stable but highly dependent on implementation
details.
5. CONCLUSION AND OUTLOOK
The outcome of this study suggests that geometric speed–up techniques are a good
basis for the computation of provably optimal connections in railroad traffic infor-
mation systems. The question raised in this paper is answered for the total travel
time: the best combinations of strategies are by far faster than is currently needed
in practice. The success of geometry–based strategies is a bit surprising, because
the underlying data is not purely geometric in nature.
Another surprising outcome of the study is that both the normal heap and
the Dial data structure only require an (amortized) constant time per operation,
whereas the worst–case bound is logarithmic for heaps and even linear for Dials.
Note that no amortization over a set of queries must be applied to obtain a con-
stant time per operation; the variance is small enough that the average run time
per operation within a single query can essentially be regarded as bounded by a
Dijkstra’s Algorithm On–Line
·
15
Selection of stations
Angle restriction
CPU heap
CPU Dial
no
no
0.204
0.072
no
yes
0.022
0.013
yes
no
0.019
0.010
yes
yes (train)
0.006
0.004
yes
yes (auxiliary)
0.005
0.003
Selection of stations
Angle restriction
Nodes
Edges
no
no
11072
20046
no
yes
3415
7120
yes
no
1437
2465
yes
yes (train)
856
2002
yes
yes (auxiliary)
754
1765
Selection of stations
Angle restriction
Ops. heap
Ops. Dial
no
no
151274
15274
no
yes
16990
2430
yes
no
18123
2595
yes
yes (train)
3502
961
yes
yes (auxiliary)
2282
751
Table 2. Like Table 1 except that now the strategy “goal–directed search” is additionally applied
in all cases.
constant. Due to the fact that the variance is negligible, a conventional statistical
analysis would not make any sense.
The choice of algorithms (and of minor details of their implementation) is justified
a posteriori in view of our main question. Implementing and comparing further
speed–up strategies is certainly an interesting topic in its own right. However, the
goal of our research effort is different: to go far beyond the restricted scenario of
Assumption 1.1 and to see which algorithms will stand this ultimate test.
The minimal travel time is certainly an empirical research topic in its own right,
not only because it is the most fundamental objective in practice. However, a
practical algorithm must consider further criteria and restrictions. For example,
the ticket costs and the number of train changes are also important objectives.
Moreover, certain trains do not operate every day (contrasting Assumption 1.1(1)),
and certain kinds of tickets are not valid for all trains, so it should be possible
to exclude train connections in a query. A satisfactory compromise must be found
between the speed of the algorithm and the quality of the result. Thus, the problem
is not purely technical anymore but also involves “business rules,” which are usually
very informal.
In the future, an extensive requirements analysis will be necessary, which means
that the work will be no longer purely “algorithmical” in nature. Such an analysis
must be very detailed because otherwise there is no hope to match the real problem.
Unfortunately, there is high evidence that the general problems addressed in [22]
will become virulent here: a sufficiently simple formal model that captures all
relevant details does not seem to be in our reach, and many details are “volatile”
16
·
F. Schulz and D. Wagner and K. Weihe
in the sense that they may change time and again in unforeseen ways. Future
research will show whether these conflicting criteria can be simultaneously fulfilled
satisfactorily.
REFERENCES
[1] R. Agrawal and H. Jagadish. Algorithms for searching massive graphs. IEEE Transact.
Knowledge and Data Eng., 6:225–238, 1994.
[2] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows. Prentice–Hall, 1993.
[3] S. Albers, A. Crauser, and K. Mehlhorn. Algorithmen für sehr große Datenmengen. MPI
Saarbrücken, 1997. 12
[4] A. Car and A. Frank. Modelling a hierarchy of space applied to large road networks. In Proc.
Int. Worksh. Adv. Research Geogr. Inform. Syst. (IGIS ’94), pages 15–24, 1994.
[5] B.V. Cherkassky, A.V. Goldberg, and T. Radzik. Shortest paths algorithms: Theory and
experimental evaluation. Mathematical Programming, 73:129–174, 1996.
[6] T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press and
McGraw–Hill, 1994.
[7] J. Hooker. Needed: An empirical science of algorithms. Operations Research, 42:201–212,
1994.
[8] J. Hooker. Testing heuristics: We have it all wrong. Journal of Heuristics, 1:33–42, 1995.
[9] K. Ishikawa, M. Ogawa, S. Azume, and T. Ito. Map navigation software of the electro multivi-
sion of the ’91 toyota soarer. In IEEE Int. Conf. Vehicle Navig. Inform. Syst. (VNIS ’91),
pages 463–473, 1991.
[10] H.F. Jackson, P.T. Boggs, S.G. Nash, and S. Powell. Guidelines for reporting results of com-
putational experiments—report of the ad hoc committee. Mathematical Programming,
49:413–425, 1991.
[11] D.S. Johnson. A theoretician’s guide to the experimental analysis of algorithms, 1996.
http://www.research.att.com/~dsj/papers/exper.ps.
[12] S. Jung and S. Pramanik. Hiti graph model of topographical road maps in navigation systems.
In Proc. 12th IEEE Int. Conf. Data Eng., pages 76–84, 1996.
[13] C.Y. Lee, J. Bard, M.L. Pinedo, and W. Wilhelm. Guidelines for reporting computational
results in iie transactions. IEE Transactions, 25:121–123, 1993.
[14] T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, 1990.
[15] C. McGeoch. Analyzing algorithms by simulation: Variance reduction techniques and simu-
lation speedups. ACM Computing Surveys, 24(2):195–212, 1992.
[16] C. McGeoch. Toward an experimental method of algorithm simulation. INFORMS Journal
on Computing, 8(1):1–15, 1996.
[17] T. Preuss and J.-H. Syrbe. An integrated traffic information system. In Proc. 6th Int. Conf.
Appl. Computer Networking in Architecture, Construction, Design, Civil Eng., and Ur-
ban Planning (europIA ’97), 1997.
[18] J. Shapiro, J. Waxman, and D. Nir. Level graphs and approximate shortest path algorithms.
Network, 22:691–717, 1992.
[19] S. Shekhar, A. Fetterer, and G. Goyal. Materialization trade–offs in hierarchical shortest
path algorithms. In Proc. Int. Symp. Large Spatial Databases, Springer Lecture Notes
in Computer Science 1262, pages 94–111, 1997.
[20] S. Shekhar, A. Kohli, and M. Coyle. Path computation algorithms for advanced traveler
information system (atis). In Proc. 9th IEEE Int. Conf. Data Eng., pages 31–39, 1993.
[21] K. Weihe. Reuse of algorithms — still a challenge to object–oriented programming. In Proc.
12th ACM Symp. Object–Oriented Programming, Systems, Languages, and Applications
(OOPSLA ’97), pages 34–48, 1997.
12Available from http://www.mpi-sb.mpg.de/units/ag1/extcomp.html. The lecture notes are in
German, however, the chapter on shortest paths (Chapter 9) is in English.
Dijkstra’s Algorithm On–Line
·
17
0
20000
40000
60000
80000
100000
120000
140000
160000
180000
0
5000
10000
15000
20000
25000
30000
0
5000
10000
15000
20000
25000
30000
35000
40000
45000
0
200
400
600
800
1000
1200
0
50000
100000
150000
200000
250000
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0
200
400
600
800
1000
1200
0
50000
100000
150000
200000
250000
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
0
200
400
600
800
1000
1200
Fig. 7. An exemplary sequence of diagrams for one particular combination of strategies: “angle
restriction” is applied, but the other strategies are not. First column: the frequency distribution
histogram of all queries in the snapshot according to (a) the number of nodes met by the search
(granularity: 500 nodes), (b) the CPU time for the heap implementation and (c) for the Dial
implementation (granularity: 10 milliseconds). Second column: the average of (a) the number of
nodes met and (b/c) the CPU times for the heap/Dial variant taken over all queries with roughly
the same resulting total travel times (granularity: 20 minutes). The strong resemblance of the
diagrams in each row nicely demonstrates the linear behavior of both priority–queue implemen-
tations.
[22] K. Weihe, U. Brandes, A. Liebers, M. Müller-Hannemann, D. Wagner, and T. Willhalm.
Empirical design of geometric algorithms. In Proc. 15th ACM Symp. Comp. Geometry
(SCG ’99), pages 86–94, 1999.
18
·
F. Schulz and D. Wagner and K. Weihe
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
Fig. 8. The relation between the number of nodes hit by the search (abscissa) and the cpu time
in seconds for the heap (left) and the Dial (right) implementation. The first row shows one point
for every query, the second row condenses this information to histograms (granularity: 500 nodes).
Dijkstra’s Algorithm On–Line
·
19
Fig. 9. The left picture shows the edges hit by Dijkstra’s algorithm from Berlin Main East Station
until the arrival station Frankfurt/Main Main Station is reached. In the right picture, the strategy
“angle selection” was applied to the same query.
20
·
F. Schulz and D. Wagner and K. Weihe
Fig. 10. The left picture shows the 225 stations selected for the study on strategy “selection of
stations,” and the right picture shows the edges hit by this strategy for the same query as in
Figure 9. In the right picture, the original train graph is shown in the background, whereas the
highlighted edges are the edges of the auxiliary graph hit by the search.
Dijkstra’s Algorithm On–Line
·
21
Fig. 11. Both pictures refer to the same query as in Fig. 9. The strategies “selection of stations”
and “angle restriction” are applied simultaneously with angles computed from the train graph
(left), and with angles computed from the auxiliary graph itself (right). Like in the previous
picture, the original train graph is shown in the background, and the highlighted edges are the
edges of the auxiliary graph hit by the search.
22
·
F. Schulz and D. Wagner and K. Weihe
Fig. 12. Both pictures refer to the same query as in Fig. 9. They show the results of the strategy
“goal–directed search” and “bidirected search,” respectively.