A Real-time Point-to-Point Shortest Path Search Algorithm Based on Traveling Time
Sang-Un Lee · 한국인터넷방송통신학회 논문지 · 2012
The shortest path search algorithm of navigation is generally based on Dijkstra algorithm and considers only the distance using the weight. Dijkstra algorithm based on the distance mainly ought to perform the `number of nodes 1` and requires a lot of memory, for it is to start from the starting node and to decide the shortest path for all the nodes. Also, it searches only the same identical path in case of any bottleneck due to an accident nearby, since it is based only on the distance, and hence does not have a system that searches the detour road. In order to solve this problem, this paper considers only the travelling time per road (travelling speed * distance), without applying speed criteria (smoothness, slow speed, stagnation and accident control) or road class (express road, national road and provincial road). This provides an advantage of searching the detour, considering the reality that there are differences in time take for the car to travel on different roads with same distance, due to any accident, stagnation, or repair construction. The suggested algorithm proves that it can help us to reach the destination within the shortest time, making a detour from any congested road (outbreak) on providing an information on traveling time continuously(real-time) even though there is an accident in a particular road.