An analysis of stochastic shortest path problems

The authors consider a stochastic version of the classical shortest path problem whereby for each node of a graph, they must choose a probability distribution over the set of successor nodes so as to reach a certain destination node with minimum expected cost. The costs of transition between successive nodes can be positive as well as negative. The authors prove natural generalizations of the standard results for the deterministic shortest path problem, and they extend the corresponding theory for undiscounted finite state Markovian decision problems by removing the usual restriction that costs are either all nonnegative or all nonpositive.