Patent ID: 6356911
Filing Date: 2002-03-12
Classification: G01C,G06F,Y10S

Abstract:
A shortest path search system for searching for a shortest path between one source and multiple destinations comprising:(1) a priority queue producer for producing a priority queue to store nodes to be searched for; (2) a node finder for locating a node v, stored in said priority queue, with which to minimize the sum of a length p(v) of a path extending between a source and said node v and a value of an estimate function h(v), obtained from a relationship between a node adjacent to said node v and a set of destinations, where h(v) is a lower bound of all the shortest path lengths extending from node v to each of the multiple destinations; (3) a node deleter for deleting said node v from said priority queue; (4) a storage means for storing said node v in an established set S of shortest paths; (5) a process terminator for terminating a search process when said multiple destinations are included in said established set S; (6) a node finder for locating all nodes w that adjoin said node v and at which a path length p(w) is equal to or greater than the sum of a path length p(v) from said source to said node v and a path length from said node v to said node w; and (7) a storage means for storing all said nodes w in said priority queue.