A polynomial-time algorithm to find Shortest Paths with Recourse

The Shortest Path with Recourse Problem involves finding the shortest expected-length paths in a directed network, each of whose arcs have stochastic traversal lengths (or delays) that become known only upon arrival at the tail of that arc. The traveler starts at a given source node and makes routing decisions at each node in such a way that the expected distance to a given sink node is minimized. We develop an extension of Dijkstra's algorithm to solve the version of the problem where arc-lengths are nonnegative and reset after each arc traversal. All known no-reset versions of the problem are NP-hard. We make a partial extension to the case where negative arclengths are present. (C) 2003 Wiley Periodicals, Inc.