Title:
METHOD AND SYSTEM FOR SEARCH OF MINIMUM-COST ROUTE
Document Type and Number:
Japanese Patent JP3495220
Kind Code:
B2
Abstract:
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.
More Like This:
| WO/2002/046963 | MAP GUIDANCE VIDEO SYSTEM |
| WO/2017/033737 | REGION GUIDANCE SYSTEM AND REGION GUIDANCE PROGRAM |
| JP5381691 | Map display device, map display method and program |
Inventors:
Keisuke Ohnishi
Arata Kikuchi
Arata Kikuchi
Application Number:
JP7910797A
Publication Date:
February 09, 2004
Filing Date:
March 14, 1997
Export Citation:
Assignee:
Navitime Japan Co., Ltd.
International Classes:
G09B29/10; G01C21/00; G01C21/34; G06F17/00; G06F17/30; G06F19/00; G06Q50/00; G06Q90/00; G08G1/00; (IPC1-7): G01C21/00; G06F17/30; G06F19/00; G09B29/10
Domestic Patent References:
| JP6273181A | ||||
| JP5107073A |
Attorney, Agent or Firm:
Masao Toyoda