This navigation apparatus includes a road setting unit that sets a road to be traversed between a departure point and a destination, the road being constituted by links for each of which a predetermined link cost is set, a replacement unit that replaces the links constituting the road to be traversed that has been set by the road setting unit, with a virtual link whose link cost is set to be smaller than the total of the link costs of the links for the road to be traversed, and a route search unit that searches for a recommended route from the departure point to the destination, based upon link costs set for links that constitute roads other than the road to be traversed, and the link cost set for the virtual link with which the road to be traversed has been replaced by the replacement unit.