The problem of adaptive routing in a network with failures is considered. The network may be in one of finitely many states characterized by different travel times along the arcs, and transitions between the states occur ...