METHOD AND SYSTEM FOR SEARCH OF MINIMUM-COST ROUTE

摘要

PROBLEM TO BE SOLVED: To obtain a method and a system in which a minimum-cost route can be searched at high speed by a constitution wherein the minimum-cost route corresponding to a target node is traced on a table which records an exit link to be used as the minimum-cost route up to all target points from a starting point. SOLUTION: A flag table (a) is created in such a way that a circle mark as a minimum-cost route contribution exit link for a target node is given to an exit link for a starting node found by a reverse route search processing operation using the Dijkstra method. As accompanying tables, a table (b) which indicates a range corresponding to an exit link for a node and a a table (c) indicating a starting-point node and an end-point node for a link are provided. When a minimum-cost route is searched, the flag table (a) is used, a minimum- cost exist link to a target point from a starting point is first found, a link corresponding to a connection node for the exit link found from the accompanying tables (b), (c) is then found, and this operation is repeated. Thereby, all links and all nodes up to a destination are detected. The respective tables (a), (b), (c) are formed as databases.