High-speed motion of vehicles and dynamic change of network topology make it difficult to design Vehicular Ad Hoc Networks (VANETs) routing protocol. The stability of routing protocol is an important guarantee for transmitting data. Therefore, a graph-based s routing strategy is proposed in this paper, which is used in Ad Hoc On-Demand Distance Vector (AODV) routing protocol. The optimal AODV routing is marked as GS-AODV. In GS-AODV, the s link model is established, and the stability of routing is computed out by speed information of vehicles. After that, the dynamic information of topology is acquired by graph theory. Finally, the most s routing is selected to transmit data. Simulation results show that the performance of proposed GS-AODV is improved in terms of packet delivery ratio, end to end relay delay, and the numbers of link failures.