Guidance systems, methods, and programs acquire, from a map information providing device, update information for updating map information that is stored in guidance memory, and update, on the basis of the acquired update information, the stored map information. The systems, methods, and programs acquire, from the map information providing device, temporarily delivered information that is used for guidance until the update is complete. The temporarily delivered information has an identical data structure to the stored map information and is replaceable with the stored map information. Until the update is complete, the systems, methods, and programs provide guidance on the basis of the acquired temporarily delivered information. After the update is compete, however, the systems, methods, and programs provide guidance on the basis of the updated map information.