Location based services (LBS) are capturing global spotlights increasingly, in which users tend to pick up navigation service as their favorites. This paper examines the dynamic routing problems based on real-time traffic information in LBS. At first, the overall structure of dynamic navigation system is illustrated, which is composed of four ingredients: traffic data collection, digital road map, static routing and dynamic re-routing. Traffic data collection is the task of traffic information center (TIC), where various sources of data are fused into link travel times that are used as criteria to choose candidates in path determining. Digital road map includes digital road network and historical traffic data, where the topology relationship of road network is elementarily explored and the method to represent statistical traffic data is referred to. Routing with historical traffic data and dynamic re-routing with live traffic data are two main functions of dynamic navigation service. The flow of dynamic re-routing algorithm is exhibited. Lastly, a first-in-first-out (FIFO) time-depend shortest path algorithm is discussed for dynamic routing, which adopts the adaptive A* algorithm based on binary heap priority queue and RB-tree.