The primary goal of navigation systems is to determine an optimal routing path to achieve the least travel time and exhausted gasoline. Most of currently navigation systems use the static shortest path routing algorithm with digital geographic map or additionally consider non real-time traffic information from a radio frequency-based centralized Traffic Information Center (TIC). Since the gathered traffic information from few monitor devices only covers some highways and from some drivers, it results in some disadvantages, including supporting partial traffic information on some special highways, long update period, inaccurate drivers report, and centralized TIC. In consequence, the determined routing path based on above traffic information results in a shortest path but can not meet the optimal demand of vehicle navigation. The proposed approach adopts IEEE 802.16j standard, i.e., multihop relay WiMAX network, as the wireless transmission network for supporting wide wireless range and extending the access areas; consequently, it guarantees the quality of wireless transmission and the accuracy of exchanged traffic information. Furthermore, the density-based coloring method to set the road weights and the rerouting mechanism are adopted for adaptive routing. Finally, the proposed approach can determine the path with the least travel time and cost as the optimal routing path. Numerical results show that the proposed adaptive navigation approach outperforms other approaches in the travel time, exhausted gasoline.