Devices, methods, and programs provide vehicle navigation. A speculative heading error is acquired that corresponds to the reliability of the vehicle heading, which corresponds to an estimated vehicle position that was calculated using a previous vehicle position as a reference. A best candidate position or the estimated vehicle position is set as the vehicle position depending on whether a heading difference between the vehicle heading and a heading when the estimated point is corrected to the best candidate position falls within the speculative heading error. Therefore, false matching can be further reduced and prompt recovery is possible even if a false match occurs.