Postal route system and method for fast algorithm of the shortest path in the same

• US 6,029,112 A
• Filed: 02/21/1997
• Issued: 02/22/2000
• Est. Priority Date: 06/12/1996
• Status: Expired due to Term

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Nam, Sang Woo, Woo, Dong Chin
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Hernandez, Olga
• Application Number:
  US08/804,269
• Time in Patent Office: 1,096 Days
• Field of Search: 701/209, 701/202, 701/210, 701/208, 701/117, 701/200, 340/990, 340/995, 364/449, 364/444
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

This invention provides a method for searching the shortest path between two points in a geographics information system. In a postal route system and method for fast algorithm of the shortest path search with direction in the same according to the present invention, in order to serve an application service associated with the method for fast algorithm of the shortest path search, a map and an associated information are constituted by a database through which the process to generate the shortest path is performed so that it is possible to provide services utilized in such as postal delivery, transport information system and general road information guide which require the information on the shortest distance.

Claims

1. A postal route system comprising:

a spacial and information database which can use both a general database management system and a database management system served from a geographics information system;

a geographics information system engine including the shortest path generation algorithm module for finding the shortest route by performing the process on the map, a coordinates value extraction, and a distance value calculation from the spacial and information database;

an application system and user interface for displaying on a screen a trace of the shortest path followed by the shortest path generation algorithm module of the geographics information system; and

a shortest path knowledge database for storing data for the trace of the shortest path obtained by the shortest path generation algorithm module and using the same,

wherein a map, diagram and node database composed of a basis layer, a read layer linking roads with nodes, and other layers representing an associated information for simultaneously processing the spacial data and information data by the spacial and information database.

2. A method for fast algorithm of the shortest path search in a postal route system comprising the steps of:

calculating coordinates of a starting point, coordinates of a destination point, and a straight line between starting and destination points;

extracting a road connected by the shortest distance between starting and destination points;

selecting a connection node in the starting point selected at present;

determining whether the current selected road is a node including an end node or not and calculating a value of straight distance between the current selected nodes and the destination point if it is determined that the current selected node is the node including the end node;

determining whether nodes with a small comparison value of the selected nodes are selected or not, storing a value of straight distance into a linked list file arranged in an ascending order if nodes with the remaining large comparison value are selected, and selecting other nodes and other connection roads if nodes with the smallest comparison value are selected; and

by analysising and checking the selected roads, selecting nodes and roads with a comparison value next to the smallest comparison value and then returning to the step of analysising and checking the selected roads, or selecting another node of a selected road if a normally selected road exists and then returning to the step of determining whether the end node is included in the road or not.