The main goal of vehicle navigation systems is to determine the optimal routing path for achieving the least travel time and exhausted gasoline. Most navigation systems use the static shortest path routing algorithm or use optional traffic information broadcasted by a centralized traffic information center (TIC) to avoid routing to heavy traffic load roads. Since the traffic information may be gathered from few monitoring devices that only covers some specific highways and roads, it results in some disadvantages, including only supporting partial traffic information on some roads, long update period and low reliability of using a centralized TIC. In consequence, the determined route could be the shortest distance route but it may not meet the demands of the optimal routing: the least travel time and exhausted gasoline. Therefore, we propose herein the wireless sensor network-based adaptive navigation approach, which uses the WiMAX multihop relay networks as the inter-vehicle communications (IVC) to increase the reliability and efficiency of inter-vehicle communications. Real-time traffic information could be gathered from various types of sensors equipped on vehicles and exchanged among neighbor vehicles. As a result, the navigation system can obtain three metrics of the road traffic density, road class and road distance to determine the optimal route. Numerical results indicate that the proposed adaptive navigation approach outperforms other approaches in the average travel time and average exhausted gasoline while yielding competitive average travel distance.