AbstractIn this article, we investigate two different recoverable robust (RR) models to deal with cost uncertainties in a shortest path problem. RR extends the classical concept of robustness to deal with uncertainties by incorporating limited recovery actions after the full data are revealed. Our first model focuses on the case where the recovery actions are quite restricted: after a simple path is fixed in the first stage, in the second stage, after all data are revealed, any path containing at most k new arcs may be chosen. Thus, the parameter k can be interpreted as a mediator between robust optimization—no changes allowed—and optimization on the fly—an arbitrary solution can be chosen. Considering three classical scenario sets, which model uncertainties in the cost function, we show that this new problem is strongly NP‐hard in all these cases and is not approximable, unless P = NP. This is in contrast to the robust shortest path problem, where, for example, an optimal solution can be computed efficiently for interval and Γ ‐scenarios. For series‐parallel graphs and interval scenarios, we present a polynomial time algorithm for this RR setting. In our second model, the recovery set, that is, the set of paths selectable in the second stage is not limited, but deviating from the previous choice comes at extra cost. Thus, a path chosen in the first stage produces renting costs modeled as an α ‐fraction of the scenario cost. For an arc taken in the second stage, the remaining cost needs to be paid in addition to some extra inflation cost modeled by a β ‐fraction of the scenario cost, if the arc was not reserved beforehand. The complexity status of this problem is similar to the robust case. Yet, for Γ ‐scenarios, the problem is again strongly NP ‐hard, but can be approximated with a \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$\min\{2+\beta,\frac{1}{\alpha}\}$\end{document} factor. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012