IEICE TRANS. , VOL. E00{D, NO. 00 1998

1

PAPER

Finding Useful Detours in Geographical Databases
Tetsuo Shibuyay , Nonmember, HiroshiyyyImaiyy , Member, Shigeki
Nishimurayyy ,yyy
Hiroshi Shimoura , and Kenji Tenmoku , Nonmembers
SUMMARY

In geographical databases for navigation, users raise various types of queries concerning route guidance. The most fundamental query is a shortest-route query, but, as dynamical trac
information newly becomes available and the static geographical database of roads itself has grown up further, more exible
queries are required to realize a user-friendly interface meetingthe current settings. One important query among them is a detour query which provides information about detours, say listing
several candidates for useful detours.
In this paper, we rst review algorithms for the shortest andk shortest paths, and discuss their extensions to detour queries.
Algorithms for nding a realistic detour are given. The eciency
and property of the algorithms are examined through experiments on an actual road network.

key words:
Geographical databases, car navigation, shortest
paths, detour query

ligence) search techniques [2]{[5], [9].

The k shortest paths problem is the generalizationof this shortest path problem. If you need \good" solutions other than the optimal one, or optimal solution
under certain constraints, it is a good news that you cannd the k shortest paths quickly. Hence, this problem

is also very applicable in many
connection routing,elds, such as networknding a detour in navigation sys-tems, DNA alignment [8], etc.

This problem is alsoa very ecient algorithm for this. According to this,for a directed graph with n vertices and non-negative

In geographical databases, various types of queriesarise, especially for spatial and topological queries. One
such typical query is a shortest-path query, which isRecently, as dynam-

ical trac information newly becomes available suchas ATIS (Advanced Trac Information Service), and
VICS (Vehicle Information & Communication System)
in Japan, more sophisticated queries come to be required. Also, the static geographical database of roads
itself has grown up further, and similarly in this respect advanced types of queries are necessary to realize
a user-friendly interface meeting the current circumstances. One important query among them is a detour
query which provides information about detours; forexample, enumerating several candidates for useful detours.
From the algorithmic viewpoint, the shortest path
problem itself has been studied very well for a longtime.

algorithm, which are often cited as AI (Arti cial Intel-

studied very well, and, recently, Eppstein has proposed

1. Introduction

crucial for car navigation, etc.

famous and traditional algorithm for this problem. To
make this algorithm more ecient, many algorithms
3
has been considered, such as the A algorithm, the3bidirectional Dijkstra method, and the bidirectional A

For example, the Dijkstra method is the mostManuscript received 1998
Manuscript revised 1998y
The author is with IBM Tokyo Research Laboratory.
This work was done while the author was at Department ofInfomation
Science, University of Tokyo.
yy
The author is with Department of Information Science,
University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 1130033,
Japan
yyy
The authors are with Sumitomo Electric Industries,
Ltd., Osaka, Japanm edges, the k shortest paths from one source to l destinations are known to be obtained in O (m + n log n + lk )time, or in sorted form in O (m + n log n + lk log k ) time

[1].
But this original algorithm requires searching with
the Dijkstra method from the source to the other all vertices. Thus, reduction of the searched region is desired,especially in case the graph is very large. This paper
extends the Eppstein's algorithm, using upper bound of
the length of the suboptimal paths and the technique3of bidirectional A algorithm, to reduce the searchedregion in the 2-terminal k shortest paths problem.

This paper then discusses the detour problem as
one of its applications.

The `detour' is a suboptimal

path which is short but overlaps little with the shortest
path. But this concept is ambiguous. Because of thisambiguity, the detour problem is not so studied as theshortest path problem.

Hence this paper de nes `de-tour' precisely, and proposes algorithms fornding arealistic detour based on previous algorithms.
Then the eciency of these algorithms are examined through experiments on an actual road networkfrom a geographical database.

2. Preliminaries
In this paper, let the graph in assumption be a directed

graph, G = (V; E ), in which l (v; w ) is the length of theedge (v; w ) which is always non-negative, and s be theIEICE TRANS. , VOL. E00{D, NO. 00 19982
source and t be the destination when we consider the
shortest path problem or the k shortest path problem.

is the temporary estimate for the shortest path from s
3to t via v . The searched vertices by the A algorithm is

Add to this, let d(u; v ) be the shortest path length fromu to v , n be jV j and m be jE j.

always within searched vertices by the Dijkstra method.
3
In this way, the A algorithm can get the shortest path

2.1

more e ectively.
3
In the A algorithm, the shortest path from s may

Dijkstra Method

not appear
The Dijkstra method is a basic algorithm to solve therst, and a shorter path may be found in

the future search, which is the reason of the removal

shortest path problem. The following is the outline ofof vertices from S in step 3.

the Dijkstra method for two-terminal problem:

rather inecient. This can be avoided if the estimator

1. Let S be the empty set, and ps (v ), the potentialof a vertex v , be +1 except for the source s. Let

ps (s) be zero.

2. Find the vertex v0 which has the minimum potential in V 0 S and add v0 to S . If v0 equals to t,

is dual feasible. The de nition of `dual feasible' is asfollows:

De nition 1: The estimator hs for the shortest path
to t is called dual feasible if and only if hs satis es thefollowing constraint:u; v ) 2 E

8(

halt.

v such that (v0 ; v ) is in E , if
ps (v0 ) + l(v0 ; v ) is less than ps (v ), replace the pathfrom s to v with the path from s to v0 and the edge
(v0 ; v ), and let ps (v ) be ps (v0 ) + l (v0 ; v ).
In this algorithm, all the searched vertices has thesource s, and the potentials of the searched vertices denote the length of the path.

be used for a dual feasible estimator in a graph of aroad network.
If the estimator is dual feasible, the A

If we do not halt until

S j be zero, we can get the shortest path tree from the

Theorem 1: Let hs be a dual feasible estimator fors. The Dijkstra method on a graph in which the length
0of the edge (u; v ), or l(u; v ) is replaced by l (u; v ) as fol3
lows is equivalent to the A algorithm on the originalgraph.

l0 (u; v ) = l(u; v ) + hs (v ) 0 hs (u)less of where the destination is, which is a disadvantageof the Dijkstra method.

3
A Algorithm

3
The A algorithm

3 algorithm

can be easily translated to the Dijkstra method by mod-source. This algorithm searches all directions regard-

2.2

(1)

ifying the length of the edges [2]:information of the temporary shortest path from thejl(u; v ) + hs (v ) >= hs (u)For example, Euclid distance between v and t can

3. For all vertices

4. Go to step 2.

It makes this algorithm

2.3

(2)

Bidirectional Methods

3
The Dijkstra method and the A algorithm are unidinds the shortest path from sources to destination t eciently, using a heuristic estimate
for the length of the shortest path to the destinationt, which is not longer than the actual shortest path tothe destination, if the estimate can be given for eachvertex[3][9]. The outline of the algorithm is as follows:
1. Let S be the empty set, and ps (v ), the potentialof a vertex v , be +1 except for the source s. Let
ps (s) be zero.

2. Find the vertex v0 which has the minimum valueof ps (v ) + hs (v ) in V 0 S and add v0 to S . If v0
equals to t, then halt.

v such that (v0 ; v ) is in E , if
ps (v0 ) + l(v0 ; v ) is less than ps (v ), replace the pathfrom s to v with the path from s to v0 and theedge (v0 ; v ), and let ps (v ) be ps (v0 ) + l(v0 ; v ), andremove v from S if v is in S .

3. For all vertices

4. Go to step 2.
In this algorithm, ps (v ) also denotes the length of
the temporary shortest path from s to v . ps (v ) + hs (v )rectional algorithms. This means one of the two vertices, that is the source or the destination, plays lessrole than the other. The bidirectional Dijkstra method
solves this problem[4][5].
In the bidirectional Dijkstra method, searches aredone both from the source and destination using theDijkstra method. In outline, the algorithm is like thefollowing:
1. Let S and T be the empty set, and the potentials

ps (v ) for s and pt (v ) for t be both +1, except forps (s) and pt (t). Let ps (s) and pt (t) be zero.
2. Add vertex v0 which has the smallest potential fors in V 0 S . Then, go to step 7 if v0 is in T .
3. For all vertices v such that (v0 ; v ) is in E , if
ps (v0 ) + l(v0 ; v ) is less than ps (v ), replace the pathfrom s to v with the path from s to v0 and the edge
(v0 ; v ), and let ps (v ) be ps (v0 ) + l (v0 ; v ).
4. Add vertex v0 which has the smallest potential fors in V 0 T . Then, go to step 7 if v0 is in S .
5. For all vertices v such that (v; v0 ) is in E , if l(v; v0 )+pt (v0 ) is less than pt (v ), replace the path from v

SHIBUYA et al: FINDING USEFUL DETOURS IN GEOGRAPHICAL DATABASES

to t with the edge (v; v0 ) and the path from v0 tot, and let pt (v ) be l(v; v0 ) + pt (v0 ).

7. Find the edge (u; v ) minimizing ps (u) + l (u; v ) +pt (v ) such that u is in S and v is in T . The shortest path from s to t consists of the path from s tou and the edge (u; v ) and the path from v to t if
ps (u) + l(u; v ) + pt (v ) is less than ps (v0 ) + pt (v0 ),otherwise it consists of the path from s to v0 andthe path from v0 to t.
The paths which pass vertices in neither S nor T

are always longer than ps (v0 ) + pt (v0 ). Thus, the obtained path is guaranteed as the shortest path.
If the graph is homogeneous, the number of vertices searched with this algorithm is half of that with
the Dijkstra method, because these searched vertices
are in two cycles whose radii in this algorithm are halfof the radius in the unidirectional Dijkstra method.
But this bidirectional Dijkstra method searches all
directions regardless of where the other terminal is. If
we have dual feasible estimators for both of the source
and the destination, we can overcome this disadvantage, using a technique like in Theorem 1 based on thefollowing theorem:

Theorem 2: By searching the shortest path with thebidirectional Dijkstra method on the graph in which thelength of edge (u; v ), or l (u; v ) is replaced by the follow0
ing l (u; v ), we can get the shortest path. Let hs and ht

be dual feasible estimators for source s and destinationt.

l (u; v ) = l(u; v ) +
+

1
2
1
2

(ht (u) 0 ht (v )) :(3)

without cycles), the best known bound isO(k (m +On the other hand, Eppstein proposednds the k shortest paths implic-

itly regardless of cycles, in time O (m + n log n + k ), orO(m + n log n + k log k ) if the output paths are sorted[1].
We discuss the latter algorithm here.
At

We can suppose a heap, in which the parent of apath p is a path which is same as p until sidetrack (p)and go along the shortest path instead of going tosidetrack (p). We de ne this parent of p as parent(p).
The root of the heap is the shortest path, and all thepath from s to t appear in the heap once. In this heap,

p is  (sidetrack (p)) longer than parent(p).
We call p-heap if the node of the heap has only pchildren at most. The basic concept of the Eppstein's
algorithm is to modify this path heap to 4-heap. Oncethe 4-heap has made, we can get the k shortest paths
in O (k ) time, or O (k log k ) time if we sort the output
paths[6]. The following is the outline of this algorithm:
1. Make the shortest path tree from all the vertices
to t by the Dijkstra method.

2. For each vertex v , construct HG (v ), that is, a 30
heap of sidetracks (u; u ), such that u is on the0
shortest path from v to t, ordered by  (u; u ) dened above, as follows:a. For each vertex v , make Hout (v ), that is a 2heap in which the root has only one child, of00sidetracks (v; v ) ordered by  (v; v ).

rst, we de ne  (u; v ) for the edge (u; v ) as fol-lows:

 (u; v ) = l(u; v ) + d(v; t) 0 d(u; t)step, see [1]. Then merge Hout (v ) and HT (v )to make HG (v ).

3. For each v in G, make a pointer from each node in
HG (v ), which represents a sidetrack (u; u0 ) in G,0
to the root of HG (u ), and de ne the length of this
4. Make a node for each v in G, and make a pointerfrom this new node to the root of HG (v ). Let thelength of the new edge be the value of the root.
Let this new graph be P(G).
nd a heap Hv (G) in P (G) for any v , thinking the root as the node made in step 4 for v , and

5. We canthe value of a node as the length from the root to
the node. Find the k smallest nodes in this virtual

heap Hv (G). There is a one-to-one correspondence

between the nodes in Hv (G) and the paths from v(4)

This  (u; v ) means how much longer it will takethan the optimal way if we go to the edge (u; v ), andtherefore this value is always non-negative.

heap made in step 2-(a). For the detail of thisnew edge as the value of the root.

nding the k shortest simple paths (i.e. paths

an algorithm which

sidetrack (p) as the nearest sidetrack to t within them.

to t ordered by the value  of the root in the

Eppstein's Algorithm

n log n)) [7].

we go along a s-t path p other than the shortest path,there must be sidetracks on the path, and we de neheap of vertices on the shortest path from v(hs (v ) 0 hs (u))(1=2)(hs (v ) 0 ht (v )), and backward (1=2)(ht (v ) 0 hs (v )).

As fornot on the shortest path tree, it is called a sidetrack. If

b. For each vertex v , make HT (v ), that is, a 2-

In this algorithm, the forward search is equiva3
lent to that of the A algorithm using estimator of

2.4

If we search by the Dijkstra method from the des-tination t, a shortest path tree to t can be made. If anedge (u; v ) is on this tree,  (u; v ) is zero. If an edge is

6. Go to step 2.

0

3

to t in G, and we can easily restore the path fromthe node of the heap.
This algorithm is very ecient fornding the kshortest paths from all the vertices to one destination,

IEICE TRANS. , VOL. E00{D, NO. 00 1998

4
or one source to the other vertices. But, for the 2-terminal problem, this algorithm may search much morevertices than necessary.

3. New Approach for the 2Terminal k Shortest
Path Problem
3.1

How to Use A

3 Algorithm

3.2

Unidirectional Method

Letting popt be the shortest s-t path, we de ne 1(p) fora s-t path p as length(p) 0 length(popt ). If we can use
 where p is within
the upper bound of this 1(p), or 1,

the k shortest paths, we can easily reduce the searchedvertices.
When we do not need paths a constant longer than
the shortest one or we only want to list the paths a con-3
How to use A Algorithm in computing the k shortest
path in 2-terminal problem is discussed in this section.
If a dual feasible estimator is given, the replace of0
the length of an edge l (u; v ) with l (u; v ) described at(2) in Theorem 1 does not change the k shortest paths:

Theorem 3: The k shortest paths from s to t on agraph in which the length of the edge (u; v ), or l (u; v )0is replaced by l (u; v ) as in (2) are same as those on theoriginal graph.

Proof:

Let p be a path from s to t, and hs be adual feasible estimator for s. Then the length of p, or
length0 (p) in new graph is described by the length of p,

XXor length(p) in the original graph as follows:

length0 (p) =(5)

According to this, all the paths on the new graph froms to t are hs (s) 0 hs (t), which is constant, shorter thanthose on the original graph. This means the k shortest paths on the new graph are same as those on the

20
The same is the case with l (u; v ) of (3) in Theorem 2:

Theorem 4: The k shortest paths from s to t in agraph, in which the edge length l(u; v ) is changed tol0 (u; v ) as in (3), are same as those in the original graph.
Proof: All the paths from s to t in the modi ed graphXX

are only a constant shorter than in the original:

length0 (p) =shortest path from s to t is discovered.

3. Search successively until a vertex v from which the longer than thatshortest path to t is more than 1

If a path passes a vertex v not in the searched re because
gion, this path is longer than length(popt ) + 1

the shortest path from v to t is longer than it. So, allthe obtained k paths are shorter than length(popt ) + 1,
which is supposed to be longer than the actual

kthshortest path. Thus, the obtained k paths are the ac-tual k shortest paths.
3.3

Bidirectional Method

The Eppstein's algorithm can be used both on the
shortest path tree from the source and on that to thedestination. Thus it is a natural idea to use a bidirectional method fornding the k shortest paths. But itneeds some modi cation to the Eppstein's algorithm.
Tosolve this problem, we propose a new path heap graph
involving another heap called Hmid . We also use 1de ned at 3.2.

l(u; v ) + h

In the algorithm, let S and T be sets of searched(u;v )2p(6)

h is constant, that is (hs (t) + ht (s) 0 hs (s) 0 ht (t))=2.
This means the k shortest paths are same in the twographs.

2. Search from t by the Dijkstra method until the

The heaps obtained by the Eppstein's algorithml0 (u; v )= length(p) + hlength of each edges as in Theorem 3.

are not enough if we use a bidirectional method.

(u;v )2p=

1. If a dual feasible estimator for t is given, replaceby Eppstein's algorithm.

(u;v )2p

original graph.

The algorithm is very simple, and the outline ofthis is as follows:

4. Find the k shortest paths in the searched region,l(u; v ) + hs (t) 0 hs (s)= length(p) + hs (t) 0 hs (s)know the value, we can use it.

from s.

l0 (u; v )(u;v )2p=

stant longer than the shortest one at most, we should be this constant. If we can know approximate
let 1
 by experience or other methods or reallyvalue of 1

2

Thus we can use either unidirectional or bidirec3 algorithm implicitly by changing the length

vertices from s and t by bidirectional Dijkstra method,

ps and pt be potentials, ds be the length of the shortest
path from s to the last vertex added to S , and dt be thelength of the shortest path from the last vertex added
to T to t. The following is the outline of the algorithm:

1. If a dual feasible estimator for s and that for t are

tional A

given, change the length of the edges as in Theo-of the edges.

rem 4.

SHIBUYA et al: FINDING USEFUL DETOURS IN GEOGRAPHICAL DATABASES

2. Search by the bidirectional Dijkstra method bothfrom s and t, until the shortest path (popt ) is discovered.

5

4. Detour Problem`Detour' is a path which is short but overlaps little with

3. Continue searching untillength(popt ) + 1.

ds + dt is longer than

the shortest path. To

nd it is very important in routenavigation systems, ATM network, and so on. We discuss how to gain this detour based on the above algo-

4. Let set of edges F be f(u; v )j(u; v ) 2 E; u 2 S; v 2

T 0 S g, and set of vertices U be fv j(u; v )2 F g. (see Figure 1) Construct heap Hmid of vertices in U ordered by the value q (v ) = ps (v )+ pt (v ).
Note that v is not in S but ps (v ) is not +1. Inthis step, if q (v ) is larger than length(popt ) + 1,
we can ignore v .

rithms.
4.1

How to Compute Overlapping Length

In searching a detour, the overlapping length of a detour with the shortest path is an important factor. Let

this value for a path p be overlap(p). This length canbe computed very fast for every path encountered insearching in the path heap graph. The following is theTSoutline of this procedure:
1. For each vertex v in V , compute the length of thepart of the v -t shortest path which overlaps withthe s-t shortest path. This can be done in O (n)time, by the depthsU

rst search on the shortest pathtree to t for example. Then, let this value be ov (v ).

t

2. For each 0 (u; v ):sidetrack(u; v ),

computefollowing 0 (u; v ) = ov (v ) 0 ov (u)Fig. 1Situation of U

(7)

3. When we search in the path heap and obtained apath p, we compute the overlap(p) as follows. Let

q be parent(p) and e be sidetrack(p).

5. Construct Eppstein's path heap graph on the

shortest path tree from s, only in Gs = (S +U; f(u; v )ju 2 S; v 2 S + U g) and on that to t onlyin Gt = (T; f(u; v )ju; v 2 T g). Then let the heap
found in the graph be Hs (v ) and Ht (v ).

6. For each v in U , make a new edge from a nodein Hmid which represents v , to the roots of Hs (v )and Ht (v ), whose length is the value  of the roots.
Then think as if there is an edge from each nodein Hs (v ) to the root of Ht (v ). (This pointer is decided when the path heap graph is searched.) The

overlap(p) = overlap(q ) +  0 (e)(8)

Note that the same technique can be easily donein the bidirectional method described in 3.3.
4.2

De nition of `Detour'`Detour' is not so clear concept. Thus we must de ne
it precisely. In easiest way, we can de ne it as follows
for example:

De nition 2: `Detour' is the shortest path which

length of it is also  of the root of Ht (v ). Note thathas overlap, which is shorter than the half of the short-the completed virtual heap is 5-heap.

est path length, with the shortest path length.

7. Find the k shortest paths from the root of the entire heap by the same way as in Eppstein's algorithm.
Notice that, in step 5, we have to construct Ht only

in T . It is because once a s-t path has gone out fromS , the rest of the path cannot pass any vertices out ofT , because ds + dt is guaranteed to be larger than any
path within the k shortest paths.
In step 4, Hmid can be constructed by the modi cation of the heap used for searching from s in step 2
and 3, which can be done in O (n) time. Add to this,step 6 can also be done in O (n) time.

But this de nition requires searching the path heap inorder until a desired path will be found, which means

it takes O (k log k ) time in checking k paths, and set is dicult. Add to this, the obtained detourting 1by this de nition may branch oand join the shortest

path many times. In the car navigation system, such a
detour is not desirable.
Taking these things into consideration, we de ne`detour' as following:

De nition 3: `Detour' is 1 longer than the shortest

path at most, branch oand join the shortest path

only once, and has the smallest overlap with the shortest path among such paths.

If several paths satis es

these constraints, choose the shortest one.

IEICE TRANS. , VOL. E00{D, NO. 00 1998

6
Notice that the detour de ned in either De nition 2

3. If the length of the vmid -t shortest path in Gt , or l,

or 3 has no cycles unless there exists a zero-length cycleis shorter than the temporary shortest overlapping

length, nd the detour between s and vmid in Gs
 0 0 l as 1.
using 1v

in the graph.
4.3

How to Obtain Detour

4. If the length of the s-vmid shortest path in Gs , or l,
is shorter than the temporary shortest overlapping

We discuss how to get the detour de ned in De nition 3,

length, nd the detour between vmid and t in Gt
 0 0 l as 1.
using 1v

in this section.
4.3.1

In step 2, we can search either Hs (v ) or Ht (v ) rst.
To make this technique more ecient, we should sort

Unidirectional method

The method to search the paths which branch oandjoin the shortest path only once in the path heap is asfollows: If u of (u; v ) = sidetrack (p) is on the shortest

path tree to t and parent(p) is not the shortest path,or popt , we only have to search children of p in HT .
This technique can be also applied in the bidirectional
method, and note that listing paths which branch oand join the shortest path i times can be done with asimilar method.
Add to this, notice that, if there is longer over-lap from s to sidetrack (p) along p than the temporary

shortest overlap, we also have to search children of p

only in HT . To make this technique more ecient, weshould not search the children of popt in HT (s) from theroot of it, but search Hout (v ) and its children from s tot along popt . The same technique can be used in

nding

v in U ordered by q (v ), and search from the vertex ofwhich q (v ) is large. This is because if q (v ) is larger, theoverlapping length tends to be shorter. In step 3 and4, use the techniques in 4.3.1.
4.3.3

Method for the planar graph

A planar graph has a good feature.

If overlap(p) islarger than overlap(parent(p)), there are three cases.

If popt and parent(p) are like in Figure 2, p must takethe form of (a), (b) or (c). If p takes the form of (a),we have to search the children of p only in HT .

Determining which form p takes is a little dicult.

But, fortunately, in most cases p takes the form of (a).
It means, if we do not require the exact detour de ned
in De nition 3, we can ignore the cases (b) and (c).

the detour de ned in De nition 2. But this technique
is dicult to use with the bidirectional method.
4.3.2

(b)

s

Bidirectional method

 is notIf the length of the edges are all integers, and 1
on the bidirectional method in 3.3. The outline of thisFig. 2algorithm is as follows:

2. Let vmid be the nearest vertex to s along popt in

U . For each vertex v in U except for vmid , do thefollowing:

 skip (b)a. If q (v ) is larger than length(popt ) + 1,
and (c).

t
the shortest pathvery large, we can compute the detour eciently based

1. Construct Hs and Ht as in 3.3.

(c)parent path(a)

Searching paths in a planar graph

The road network is not a planar graph, but property of it is similar to it.

Hence, this technique may

have some e ect on the road network.

5. Experiments on Road Network
In this section, we investigate the eciency of algo-

 0 be 1
 0 q (v ). Search H (v ) for s-v pathsb. Let 1svrithms described above through experiments on the ac-

 0 longer than the shortand not more than 1vters region in Tokyo metropolitan area. As the length

which branch opopt only once as in 4.3.1,

est s-v path in Gs . At the same time, make a
 0 + 1 and ll in T [i]table Tv whose size is 1vv

the path whose overlapping length with po pt

is the shortest among the paths s.t. 1(p) <= i.

c. Search Ht (v ). Note that, for some i, if there
is no path in Tv [i] or the overlapping length ofthe path in Tv [i] is longer than the temporary

shortest overlapping length, or l , we only haveto search paths less than l 0 i longer than thev -t shortest path.

tual road network of 160 kilometers times 80 kilomeof each edge, we used the necessary time (seconds) topass the edge, which is rounded oto an integer, rather

than the distance along the edge. Accordingly, we used

Euclid distance to t and from s divided by the maxi-

mum speed, that is 105 kilometers per hour, as hs and

ht .

5.1

Property of the Road Network

Figure 3 shows 1 of the k th shortest path in case of
Hamadayama to Hongo. According to this, 1 increases

SHIBUYA et al: FINDING USEFUL DETOURS IN GEOGRAPHICAL DATABASES

in proportion to log k . This may help the estimation of used in Section 3.
1
(sec)

140

120

7

Table 2

Searched nodes by various algorithms

klength
Dij.
(b)
A3
(b)
Bi-Dij. (f)(b)
Bi-A3 (f)
(b)

1
10
100
1000
2165 2170 2184 2203
11162 11203 11305 11422
5816 5871 6034 6252
2812 2812 2882 3011
2794 2794 2874 3012
1325 1325 1388 1557
1352 1352 1402 1555

10000
2224
11545
6542
3135
3150
1752
1743

100

According to this table, the number of the searchednodes by the bidirectional method is about half of that80by the unidirectional method in both of the cases using
3
A algorithm and Dijkstra method. On the other hand,3
the number of them using A algorithm is also about3
half of that not using A algorithm in both of the cases

60

40

unidirectional and bidirectional. Accordingly, the algo3
rithm using the bidirectional A algorithm is far better

than those of the others. But, as k increase, the e ect3of the bidirectional A algorithm seems to decrease, so

20

0
1

10

100

Fig. 3

1000

10000

100000k

Relation between the k and 1

In the algorithms in Section 4, we search paths regardless of cycles. If there are many paths with cycles

it may not so ecient if k is enormously large. To sum
3
algorithm is best, as longup, using the bidirectional A

as k is not much larger than the size examined in thisexperiment.
5.3

Eciency of the algorithms for the Detour Problem

among suboptimal paths, the algorithms may not work
well, because the detour de ned by De nition 3 has no

Table 3 shows the eciency of algorithms in cases (1)cycle. Table 1 shows the ratio of paths with cycles in

Hamadayama-Hongo and (2) Sayama-Matsudo. In the longer thantable, (a) is the number of paths at most 1

the suboptimal paths whose 1's are smaller than 100,in cases (a) Yumenoshima - Hongo (b) Narita - Ichiharaand (c) Sayama - Chosi.

Table 1
s-t
(a)
(b)
(c)

The number of paths within 1 < 100d(s,t)
1010
2851
8769

] paths
780299202531674630] paths with cycles (%)
14828 (1.9%)
17857 (8.8%)111644 (16.5%)

According to this table, the paths with cycles are
relatively rare among the suboptimal paths. This table also shows that the number of suboptimal paths
increases in cases such that the paths passes the urban
areas or the distance between the terminals is large.
The example (a) is the former case and (c) is the latter
case.
5.2

Eciency of the Extended Eppstein's Algorithm

Table 2 shows the number of the searched nodes innding the k shortest path in case of Hamadayama to

Matsudo. Note that (f ) means forward search and (b)means the backward search.

In this experiment, we soused the actual 1 of the k th shortest path as 1,that we can evaluate the best case of these algorithms.

popt , (b) is that of paths who branch oand join poptamong them, (c) is that of searched paths by the algorithm in 4.3.1, (d) and (e) are those of searched pathsby the algorithm in 4.3.2. In (d), we searched Hs
and in (e), Ht

rst,

rst. (f ) is the overlapping length withpopt of the obtained detour and its ratio to the lengthof popt .

Table 3

Searched paths by various algorithms(1) Hamadayama - Hongo (length(popt ) = 891)

20
40
60
80
100
120
1
(a)
11
48
261 1180 5115 20246
(b)
9
35
185
869
3880 15348
(c)
1
6
67
375
1979 8109
(d)
2
14
97
362
1542 5883
(e)
2
28
94
237
891
3115
157
157
58
58
58
58
(f)
(17.6%)(17.6%)(6.5%) (6.5%) (6.5%) (6.5%)(2) Sayama - Matsudo (length(popt ) = 3256)
20
40
60
80
100
120
466
7174 61544 418016 2406750 12474190
(b)
108
324
1078
3259 12638 63811
107
273
954
3004 11973 37466
(c)
(d)
69
136
451
1290
5395
8689
69
136
451
1295
5379
8670
(e)
3159 1837
1837
1837
1753
1201
(f)
(97.0%)(56.4%) (56.4%) (56.4%) (53.8%) (36.9%)
1(a)

IEICE TRANS. , VOL. E00{D, NO. 00 1998

8
According to 5.1, the farther the 2 terminals are,the more suboptimal paths exists. In algorithm in 4.3.2,
if we search Hs

rst, the searched paths in Ht is re is large in
Add to this, if 1

duced, and vice versa.

compared with the distance of two terminals, the vertices in U may be nearer to t than to s. It means that
we should search Ht

Table 4 shows the e ect of this technique.

(1) Hamadayama to Hongo and (2) Sayama - Matsudo(same cases as in Table 3) by the algorithms (a) unidirectional method and (b) bidirectional method search-ing Htrst in such a case. This can be is larger than 80
seen in the case (1) especially when 1
seconds.

rst.

Table 4E ect of the technique in 4.3.3.


20 40 60 80
100
120
1
6 67 374 1952
8000
(1) (a) 1(b) 2 26 81 190 580
1658(2) (a) 107 261 808 2443 10290 313163(b) 68 133 385 1018 4472 24321* Failed nding the optimal solution

But in case of (2), such phenomenon is notseen because the distance of the 2 terminals is muchlarger.
According to the table, in general, the best method

is to use the algorithm in 4.3.2 and search Ht

Thistable shows the number of searched paths in cases ofrst, butthere are some cases that another algorithm is better.
Figure 4 shows the obtained detour from Sayama is 100 seconds and 120 seconds.
to Matsudo when 1
In thegure, the thickest line is the shortest path, andthe relatively thinner line which branch o

it is the ob-tained detour. Note that the left terminal is Sayama
and the other Matsudo.

According to this, in most cases, the optimal detour is obtained, and the number of the searched paths
are decreased. But in computing the detour from Sa is 120 by the algorithm (b),yama to Matsudo when 1
we failed nding the optimal one but the same one as = 100. Figure 4 shows the reason of this. The
when 1

In a road network, intersections cannot be nodes in is 120. Suchdetour crosses the shortest path when 1

the graph, for the reasons that costs of turning left orpaths are dicult to obtain with this technique. Add toright or going straight in intersections di er, we cannot

this, we searched with this technique much more paths

make U-turn in most intersections, and so on. Accord-than without it in this case. It is because we failed toingly, we let a node in the graph be one side of a roadnd the path which has little overlap with the shortest

segment between intersections. Hence, in a road net-

path, and as a result of it, we could not cut away thework, the detour de ned in De nition 3 can cross theunnecessary paths in searching.

shortest path at intersections.

Thus, it is not strongly recommended to apply thisThe road network is not a planar graph, but wetechnique to the road network. But if we deal with amust examine the e ect of the technique in 4.3.3 be-planar graph, we should take this technique into con-cause the road network may have a feature similar to asideration.

planar graph.

6. Conclusions
In this paper, we

rst reviewed algorithms for the short3
est path problem such as the Dijkstra method, A algorithm, bidirectional Dijkstra method, and bidirectional
3
A algorithm, and also discussed about Eppstein's al-

gorithm which is for the k shortest paths problem.

Based on these algorithms, we proposed how to im-prove Eppstein's algorithm for the 2-terminal k shortest
paths problem, using the upper bound of the length of = 100(1) 1

the k th shortest path. We rst showed we can use the3
A algorithm in nding the k shortest paths both in
the unidirectional method and in the bidirectional one.
Then, we extended the Eppstein's algorithm to use withthe bidirectional methods.
For the application of these algorithms, we discussed on the detour problem. This problem is a problem ofnding a short path which overlaps little withthe shortest path. First, we de ned what the `detour'
is, and then proposed the algorithms to

nd it.

We

described a technique when we use the unidirectional

 = 120(2) 1

Fig. 4

Detour between Sayama and Matsudo

method, then another algorithm using the bidirectional
method which can be used under certain constraints,
and an approximate method for the problem in a planar graph.

SHIBUYA et al: FINDING USEFUL DETOURS IN GEOGRAPHICAL DATABASES

These algorithms are examined in the experimentsin the actual road network.

For the k shortest path

problem, if a proper upper bound of the k th shortest

path length are given, the extended Eppstein's algo3
rithm using bidirectional A algorithm showed the best
performance. For the detour problem, the method using the bidirectional method is more ecient than theother algorithms in most cases.

In this problem, theapproximate technique for a planar graph is not so effective for the road network which is not a planar graph.
Constructing an ecient algorithm for the 2-termi
nal k shortest path problem without using the value 1,
and algorithms

t for the road network, which is con-structed on hierarchical structures, for various problems
like described above are remained as a future work.
The algorithmic results in this paper surely enhance the advanced use of geographical databases.

References[1] D. Eppstein. \Finding the k Shortest Paths", SIAM J.
Computing, 1998, to appear.
[2] T. Ikeda, M.-Y. Hsu, H. Imai, S. Nishimura, H. Shimoura, T.
Hashimoto, K. Tenmoku and K. Mitoh. \A Fast Algorithm
For Finding Better Routes By AI Search Techniques", IEEE
VNIS'94, 1994, pp.291{296.
[3] P. E. Hart, N. J. Nillson and B. Rafael, \A Formal Basisfor the Heuristic Determination of Minimum Cost Paths",
IEEE Trans. Sys. Sci. and Cyb. SSC-4, 1968, pp.100{107.
[4] T. Hiraga, Y. Koseki, Y. Kajitani and A. Takahashi, \AnImproved Bidirectional Search Algorithm for the 2 Terminal
Shortest Path" (in Japanese), The 6th Karuizawa Workshop
on Circuits and Systems, 1993, pp.249{254.
[5] M. Luby, and P. Ragde, \A Bidirectional Shortest Path Algorithm With Good Average-Case Behavior", Proc. 12th
International Colloquium on Automata, Languages and Programming, LNCS 194, 1985, pp.394{403.

[6] G. N. Frederickson. \An Optimal Algorithm for Selection
in a Min-Heap", Information and Computation, 104, 1993,
pp.197{214.
[7] N. Katoh, T. Ibaraki and H. Mine, \An Ecient Algorithm for K Shortest Simple Paths", Networks, vol.12, 1982,
pp.411{427.
[8] T. Shibuya and H. Imai, \New Flexible Approaches for Multiple Sequence Alignment", J. Computational Biology, vol.4,
no.3, 1997, pp.385{413.
[9] P. H. Winston, \Arti cial Intelligence", Addison-Wesley,
1977.

9