In this paper, we introduce a trajectory-based nonadiabatic dynamics algorithm which aims to correct the well-known overcoherence problem in Tully's popular fewest-switches surface hopping algorithm. Our simultaneous-trajectory surface hopping algorithm propagates a separate classical trajectory on each energetically accessible adiabatic surface. The divergence of these trajectories generates decoherence, which collapses the particle wavefunction onto a single adiabatic state. Decoherence is implemented without the need for any parameters, either empirical or adjustable. We apply our algorithm to several model problems and find a significant improvement over the traditional algorithm.