- - - Method to get an shortest path for Turn-restriction U-turn and P-turn in Traffic Network using Dijkstra and Floyd-Warshall Algorithm

摘要

PURPOSE: A method for calculating the shortest path by using the Dijkstra algorithm with consideration of a rotation inhibition, a U-turn and a P-turn or the Floid Washall algorithm is provided to efficiently calculate the shortest way on a traffic network. CONSTITUTION: The method comprises the steps of selecting a starting area and a Destination(501), allocating a virtual arc value based on the traffic information in preparation for a rotation inhibition, a U-turn or a P-turn, selecting the shortest travel time among the entire travel time of a temporarily labeled node(502), applying a permanent label to the selected time, and determining the shortest path by tracking a permanent node starting from a destination node. If an arc for connecting corresponding nodes exists and the virtual arc value is lower than an existing arc value, the virtual arc value is used to calculate the shortest path. Otherwise, the existing arc value is used to calculate the shortest path.