Abstract: The shortest path algorithms used widely by dynamic route planners only consider traffic information at some definite moment so as to ignore the fact that the travel time along a link is dependent on the time to enter it. Besides, those traditional node-labelling shortest path algorithms are no longer effective in view of turn delays at intersections (or nodes). In this paper, a link-based time-dependent network model is built by re-defining the First-In-First-Out (FIFO) condition with turn delay time introduced into, and then a link-labelling time-dependent A* shortest path algorithm is developed by expanding the evaluation function to time dimension and applying Euclidian distance divided by maximum possible driving speed as the heuristic evaluator. An experiment on the real road network shows that the proposed algorithm is capable of forecasting and bypassing those forthcoming traffic congestions and then shortening travel time, only with a cost of about 10 percent more computational time than the traditional algorithms. Moreover, it is able to improve overall efficiency of route planning heavily because of its no longer need to the frequent path re-optimization processes.