A method, medium, and system providing an updating traveling route to a user. The navigation system includes a route selecting unit to select an optimal route for an item to traverse based on calculated performance indexes of a plurality of alternative routes for the traversal, a performance index calculating unit to recalculate the performance indexes of the alternative routes during a current traversal of the selected optimal route based on received external information regarding sections of available traversals after a predetermined point in each alternative route beyond a current point of the current traversal, and a route changing unit to selectively update the optimal route during the current traversal based on the recalculated performance indexes.