Vehicular ad hoc networks (VANETs) are the specific class of Mobile ad hoc networks (MANETs). Since vehicles tend to move in a high speed, the network topology is rapidly changed. Thus vehicle's connectivity problem is one of the interesting issues in VANETs. Ad hoc on-demand multipath distance vector (AOMDV) is the extended version of ad hoc on-demand distance vector (AODV). AOMDV is designed to overcome a connectivity problem due to highly dynamic network topology. It provides multipath for data packets delivery from the source to the destination. Although AOMDV outperforms AODV in packet delivery ratio, AOMDV's multipath establishment and maintenance generate more control packets than AODV's unipath. However increasing the vehicle speed will degrade their performance. Thus in this paper, we added probabilistic relay, which enables adjacent vehicles to probabilistically relay unsuccessful data packet transmission, into IEEE 802.11 as a MAC standard model and combined AODV with probabilistic relay (AODV-PR) and AOMDV with probabilistic relay (AOMDV-PR). Based on our simulation result, the addition of probabilistic relay clearly helps those protocols to improve their performances especially in packet delivery ratio even under a high speed. Moreover, probabilistic relay adds beacons, but no additional routing overhead. Probabilistic relay, clearly solved connectivity problem in highly dynamic topology of VANETs. We evaluate those protocol performances based on packet delivery ratio, routing overhead, and average delivery delay under variation of vehicle speed.