  In this paper we consider shortest path problems in a directed graph where
the transitions between nodes are subject to uncertainty. We use a minimax
formulation, where the objective is to guarantee that a special destination
state is reached with a minimum cost path under the worst possible instance of
the uncertainty. Problems of this type arise, among others, in planning and
pursuit-evasion contexts, and in model predictive control. Our analysis makes
use of the recently developed theory of abstract semicontractive dynamic
programming models. We investigate questions of existence and uniqueness of
solution of the optimality equation, existence of optimal paths, and the
validity of various algorithms patterned after the classical methods of value
and policy iteration, as well as a Dijkstra-like algorithm for problems with
nonnegative arc lengths.
