| 摘要 |
In providing a method for finding a shortest path from a starting place to a destination place in a traffic network including turn restrictions, U-turns and P-turns using a Dijkstra algorithm and a Floyd-warshall algorithm, the Dijkstra algorithm includes the steps of: assigning a virtual arc connection value from a starting node to a destination node based on traffic information in order to do the turn restriction, the U-turn and the P-turn, wherein the starting node indicates the starting place and the destination node indicates the destination place; selecting a smallest travel time value out of total travel time value for a temporary label node from the starting node to all nodes except for the starting node and assigning the smallest travel time value to a permanent label node; and determining the shortest path by tracing a permanent node stating from the destination node. The Floyd-warshall algorithm includes the steps of: computing a travel time value between two nodes for all pairs of nodes; if a left-turn restriction is included in continuous three nodes, adding a virtual node L' in the continuous three nodes, wherein let the three nodes be nodes V, L and W; computing matrix of the pairs of nodes based on the virtual node L'; and finding a smallest travel time using the matrix of the pairs of nodes.
|
