Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-11
2002-03-12
Amsbury, Wayne (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06356911
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a shortest path search system, and in particular to a method and a system for searching for the shortest path between multiple nodes.
2. Related Art
The problem of finding the shortest path between multiple nodes is a problem for which a set of a plurality of sources and a set of a plurality of destinations are provided, and the shortest source-destination path is found for each source paired with each of the destinations in the set of destinations. Therefore, when there are n source nodes and m destination nodes, the shortest path must be found for n×m pairs of sources and destinations. Nodes that are included in both the source set and the destination set may be present. The Dijkstra method is known as the only method available for calculating the shortest paths between a single source and multiple destinations on a directed graph having a non-negative edge length. For reference, the pseudo code of the Dijkstra method is described below.
1×NshortestPath (source s, destination set T)
{
S and queue (PriorityQueue) are empty
for (all nodes v) path p(v) = +∞;
Enter source s in priority queue.
path p(s) = 0;
while (priority queue is not empty) {
Delete, from priority queue, node v having
smallest path p(v) value.
Enter v in established set S.
if (established set S includes destination set T)
break.
for (all edges e (destinations w) having v as
a source) {
if (p(w) > p(v) + edge length (e)) {
p(w) = (p(v) + edge length (e);
Enter w in priority queue.
}
}
}
}
Conventionally, the number of times the Dijkstra method is repeated is equivalent to the count of the multiple sources for which the shortest paths to multiple destinations are calculated. This method is also employed for various types of navigation systems. A method for increasing the speed of the Dijkstra method is not yet to be proposed.
SUMMARY OF THE INVENTION
It is, therefore, one object of the present invention to provide an efficient method and system for searching for the shortest path between a source and multiple destinations.
It is another object of the present invention to provide a method and a system for searching for the shortest paths between multiple sources and multiple destinations.
It is an additional object of the present invention to resolve a path searching problem within a short period of time when searching for the shortest path between multiple nodes.
It is a further object of the present invention to provide a search method and a search system with which optimality is not lost during a search for the shortest path between multiple nodes.
To achieve the above objects, according to the present invention, the speed of the conventional Dijkstra method, which is the basic calculation method, is increased by employing information concerning the relationship between a node and a set of destinations on a graph. The relationship information is constituted by the estimate function h(v) concerning a specific node v and a destination sets T, where h(v) is a lower bound of all the shortest path lengths extending from node v to each of the destination sets T.
In the present invention, calculation of an estimate function h(v) that satisfies the above condition is performed to obtain a value called an estimate function since an evaluation to determine the shortest path is performed during the calculation. The employment of the estimate function can increase the speed of the Dijkstra method. The lower bound is a specific value equal to or less than the smallest value.
FIG. 2
is a flowchart according to the present invention for searching for the shortest paths between a single source and multiple destinations. First, at block
210
a priority queue is prepared in which a node to be searched for is entered. At block
220
is specified a node v, entered in the priority queue, at which is minimized the sum of a path length p(v), between the source and the node v, and the lower bound h(v) of the shortest path of those for the nodes that adjoin the node v. When node v is specified in this manner, a specific direction characteristic can be provided for the extension of the search direction. At block
230
, node v is deleted from the priority queue, and at block
240
, node v is stored in the established set S, a set of solutions of the shortest paths. A check is then performed to determine whether all the destinations are included in the established set S (block
250
). When all the destinations are stored, the shortest path search is terminated. At block
260
, each node w is specified at which a path length p(w) is equal to or greater than the sum of a path length p(v) between the source and node v and a path length between node v and the specified node w. Finally, at block
270
all nodes w are entered in the priority queue, and program control returns to block
220
.
REFERENCES:
patent: 4987536 (1991-01-01), Humblet
patent: 5872773 (1999-02-01), Katzela et al.
patent: 5978732 (1999-11-01), Kakitani et al.
patent: 6016306 (2000-01-01), Le Boudec et al.
patent: 6029112 (2000-02-01), Nam et al.
patent: 6098107 (2000-08-01), Narvaez-Guarnieri et al.
patent: 6269363 (2001-07-01), Matias
patent: 405240652 (1993-09-01), None
Liu et al., “Integrating case-based reasoning, knowledge-based approach and Dijkstra algorithm for route finding”, IEEE, 1994, pp. 149-155.*
Thorup, “Undirected single source shortest paths in linear time”, IEEE, 1997, pp. 12-21, 1997.*
Han, “A new treatment of priority-first search maximum-likelihood soft-decision decoding for linear block codes”, IEEE, 1997, pp. 394.*
Cormen et al., “Algorithms”, McGraw-Hill Book Company, 1989, pp. 514-549.*
Thorup, “Undirected single source shortest paths in linear time”,IEEE, Oct. 1997, pp. 12-21.*
Liu et al., “Finding the shortest route using cases, knowledge, and Djikstra's algorithm”, IEEE, 1994, pp. 7-11.
Amsbury Wayne
Drumheller Ronald L.
Pardo Thuy
LandOfFree
Shortest path search system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shortest path search system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shortest path search system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2883223