Shortest path when allowed to reverse an edge

Question

We're given an unweighted directed graph with vertices $V$ and edges $E$. We're trying to find the shortest path from $s$ to $t$ but we're allowed to travel along up to one edge in the wrong direction.

If we insist on using all edges in the correct direction, we can solve this using BFS algorithm with $O(|V| + |E|)$ complexity. There's a brute-force solution by reversing each edge in turn and using BFS on each resulting graph, but that takes time $O(|V|\,|E|+|E|^2)$, which is rather inefficient. Is there a faster solution? I Googled and couldn't find something similar, thanks for your attention and help.

_{I cannot provide any source URL, because it seems that it is a an example of "oral folk arts".}

Answer 1

This is one of a class of similar problems which can all be handled by deriving a graph $G' = (V', E')$ from the original graph $G = (V, E)$ and then using the standard algorithm on $G'$.

Consider that at any point in your search in $G'$ you need the path information you would have at a corresponding point in the search in $G$ plus the knowledge of whether or not you have already used the bonus ability. Therefore what should $V'$ be? And following on from that, what should $E'$ be?