1. A destination prediction device that predicts a destination, comprising: a map information accumulation unit configured to accumulate map information including positions of a plurality of predetermined points and road information between the plurality of positions; a start position acquisition unit configured to acquire a start position of a mobile body; a current position acquisition unit configured to acquire a current position of the mobile body; a destination candidate position acquisition unit configured to acquire, based on the acquired start position and the current position, positions of a plurality of destination candidates that may potentially become destinations of the mobile body from said map information accumulation unit; a circuitousness calculation unit configured to calculate a circuitousness that is a deviation in route cost between (1) a route from the start position to the position of the destination candidate which passes through the current position and (2) a route capable of arriving at the position of the destination candidate from the start position at a minimum route cost; and a destination prediction unit configured to predict, as the destination, a destination candidate whose calculated circuitousness is the smallest among the destination candidates.