Provided is a navigation server capable of improving reliability or estimation accuracy of traffic state information for a user in view of the present traffic state. A partial movement cost Cik being each of movement costs in plural partial links Lik constituting a designated link Li is used to determine a total movement cost Ci in the designated link Li. The higher an occupancy ratio r of a first partial link Lim among a series of the partial links Lik, the more preferentially a partial movement cost Cim in the first partial link Lim is used than a partial movement cost Cin in a second partial link Lin to determine the total movement cost Ci of the designated link Li. In particular, only the partial movement cost Cim in the first partial link Lim is used to determine the total movement cost Ci of the designated link Li.