A navigation server (100) evaluates a transition cost δk from a reference line to each kth (k=1˜n) link via one node on the basis of a deviation of a first movement cost c1k per unit length of the kth link from the minimum value of the first movement cost c1k per unit length of all kth links. Furthermore, a second movement cost c2k corresponding to a net movement cost in each link can be evaluated on the basis of the first movement cost c1k in each link and the transition cost from the reference link to each link. When an evaluation result or a road traffic information based on the evaluation result is provided, a navigation apparatus can be make to guide a vehicle (2) according to a proper navigation route in view of real road traffic conditions.