![](https://csdnimg.cn/release/download_crawler_static/86332504/bgd.jpg)
containing the distance from
v
to vertices in a small subset of such paths. The labels are
such that any shortest
s
–
t
path can be expressed as
s
–
u
–
w
–
t
, where
u
–
w
is a subpath of a
path
P
that belongs to the labels of
s
and
t
. Queries are thus similar to HL, finding the
lowest-cost intersecting path. For efficient preprocessing, the algorithm uses the pruned
labeling technique [12]. Although this method has some similarity with Thorup’s distance
oracle for planar graphs [245], it does not require planarity. PHL has only been evaluated
on undirected graphs, however.
2.6 Combinations
Figure 6.
Illustrating a TNR
query. The access nodes of
s
(
t
)
are indicated by three (two) dots.
The arrows point to the respective
rows/columns of the distance table.
The highlighted entries correspond
to the access nodes which minimize
the combined s–t distance.
Since the individual techniques described so far exploit
different graph properties, they can often be combined for
additional speedups. This section describes such hybrid
algorithms. In particular, early results [161, 235] consid-
ered the combination of Geometric Containers, multilevel
overlay graphs, and (Euclidean-based) A* on transporta-
tion networks, resulting in speedups of one or two orders
of magnitude over Dijkstra’s algorithm.
More recent studies have focused on combining hierarchi-
cal methods (such as CH or Reach) with fast goal-directed
techniques (such as ALT or Arc Flags). For instance, the
REAL algorithm combines Reach and ALT [149]. A ba-
sic combination is straightforward: one simply runs an
ALT query with additional pruning by reach (using the
ALT lower bounds themselves for reach evaluations). A
more sophisticated variant uses reach-aware landmarks:
landmarks and their distances are only precomputed for
vertices with high reach values. This saves space (only a
small fraction of the graph needs to store landmark dis-
tances), but requires two-stage queries (goal direction is
only used when the search is far enough from both source and target).
A similar space-saving approach is used by Core-ALT [40, 88]. It first computes an
overlay graph for the core graph, a (small) subset (e. g., 1 %) of vertices (which remain after
“unimportant” ones are contracted), then computes landmarks for the core vertices only.
Queries then work in two stages: first plain bidirectional search, then ALT is applied when
the search is restricted to the core. The (earlier) HH* approach [95] is similar, but uses
Highway Hierarchies [225] to determine the core.
Another approach with two-phase queries is ReachFlags [40]. During preprocessing, it first
computes (approximate) reach values for all vertices in
G
, then extracts the subgraph
H
induced by all vertices whose reach value exceeds a certain threshold. Arc flags are then
only computed for H, to be used in the second phase of the query.
The SHARC algorithm [39] combines the computation of shortcuts with multilevel
13