SHORTEST PATH SEARCHING SYSTEM

摘要

PROBLEM TO BE SOLVED: To provide a highly efficient method to decide the shortest path between a single start point and each of plural end points by searching the shortest path starting from a single start point to each of plural end points. SOLUTION: A sequence queue is produced to store the points to be searched (210). Then the a point (v) where the sum of the path length p(v) covering a start point through the point (v) stored in the sequence queue and the lower limit value h(v) of the shortest path length among all points that are adjacent to the point (v) is minimized (220). Then the point (v) is deleted from the sequence queue (230) and stored in a definite set S (240). It's decided whether all end points are stored in the set S (250). If all end points are stored in the set S, the searching of the shortest path is ended. If all end points are not stored in the set S, all points (w) where the sum of the path length p(v) and the path length covering the start point through the point (v) is smaller than the length p(w) are specified (260). Then the points (w) are stored in the sequence queue (270) and the processing is returned to a block (220).