This paper studies the problem of finding the trajectory-adaptive routing policies with minimum expected disutility in a stochastic time-dependent network where all link travel times are temporally and spatially correlated. It is shown that Bellman’s principle is invalid if the optimality or non-dominance of a routing policy and its sub-policies is defined with respect to the universal set of travel time probabilistic outcomes. An exact algorithm is designed to find optimal trajectory-adaptive routing policies based on a new property for which Bellman’s principle holds. A comparison is made between the results of the optimal trajectory-adaptive routing policies and the optimal paths in the same test networks to investigate the benefit of being adaptive to information.