  In this paper, the recoverable robust shortest path problem under interval
uncertainty representations is discussed. This problem is known to be strongly
NP-hard and also hard to approximate in general digraphs. In this paper, the
class of acyclic digraphs is considered. It is shown that for the traditional
interval uncertainty, the problem can be solved in polynomial time for all
natural, known from the literature, neighborhoods. Efficient algorithms for
various classes of acyclic digraphs are constructed. Some negative results for
general digraphs are strengthened. Finally, some exact and approximate methods
of solving the problem under budgeted interval uncertainty are proposed.
