Stochastic Shortest Paths with Recourse

This paperc onsidersS tochasticS hortestP ath( SSP)p roblemsi n probabilisticn etworks.A variety of approaches have already been proposed in the literature. However, unlike in the deterministic case, they are related to distinct models, interpretationsa nd applications.W e have chosent o look at the case where detours from the original path must be taken whenever the "first-choice" arc fails. The main results obtained include the proof of some counterintuitive facts (e.g., the SSP may contain a cycle), the proof of the validity of applying stochasticp rogrammingt o this problem and the proof that the computational complexity of a particular SSP problem is polynomial.