5
$\begingroup$

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".

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I love the way you gave a way to approach the problem, without "giving away" the answer to an exercise-style problem and still leaving the poster the opportunity to have the pleasure of finding a full solution themselves! Great answer! $\endgroup$ – D.W. Dec 9 '18 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.