Traffic congestion arises to be a very serious problem especially in metropolitan cities nowadays. Drivers need to spend more time to their destinations. In this paper, a dynamic navigation protocol, called STN, is proposed to search for time-efficient paths for autonomous driving vehicles toward their given destinations. The trajectory information of vehicles is maintained in a server to assist the planning of navigation path. With STN, a vehicle sending a request message toward the nearest access point (AP) to acquire the driving path. By comparing the trajectories and time information in the system, the future traffic load can be predicted. The traffic load information enables the server to estimate driving speed within different paths toward the destination and then determines a time-efficient path. In addition, adjustment, update, and replan mechanisms are developed to reduce the deviation of prediction. To evaluate the performance of STN, the real road map of Shalu, Taiwan, including 20 road segments, is used. The simulator Estinet, formerly known as NCTUns (National Chiao Tung University Network Simulation) has been used for the validation of STN. The simulator integrates some traffic simulation capabilities, such as road network construction and vehicles mobility control, in the recent version. The simulation results demonstrate that STN saves around 14% driving time as compared with Vehicle-Assisted Shortest-Time Path Navigation (VAN).