公开(公告)号：US06564145B2

公开(公告)日：2003-05-13

申请号：US09752324

申请日：2000-12-27

申请人： Hong-Soo Kim ,  Jong-Hyun Lee ,  Youn-Suk Jeong

发明人： Hong-Soo Kim ,  Jong-Hyun Lee ,  Youn-Suk Jeong

IPC分类号： G01C2123

CPC分类号： G01C21/3446 ,  G01C21/34

摘要： A method is presented for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Dijkstra algorithm. The method as sets a virtual arc between nodes, and assigns a virtual arc value. A smallest travel time value is selected out of total travel time values for all nodes except for the starting node, by considering existing arcs between nodes and the virtual arc and assigning the smallest travel time value to a permanent label node. The shortest path is determined by tracing the permanent nodes starting from the destination node.

摘要翻译： 提出了一种用于从包括一个或多个匝限制，一个或多个匝数以及一个或多个P匝使用Dijkstra算法的交通网络中的起始地点到目的地地点找到最短路径的方法。 该方法在节点之间设置虚拟弧，并分配虚拟弧值。 通过考虑节点之间的现有弧和虚拟弧，并将最小的行进时间值分配给永久标签节点，除了起始节点之外的所有节点的总旅行时间值中，选择最小行进时间值。 通过跟踪从目的地节点开始的永久节点来确定最短路径。