2
$\begingroup$

I am trying to solve the following problem: Given a directed graph, there is a robot in the start and it needs to reach the destination. Each movement takes 1 second, and every second the graph reverses each edges. The robot can stay at a node and wait for 1 second in order for the graph to reverse again. The goal is to reach the destination in the shortest time possible.

Obviously since each movement takes 1 second, we can assume that each movement doesn't cost anything, but the fact that in every second the graph reverses its edges still remains. Also, since the graph is not weighted, I think Dijkstra's algorithm is not very suitable.

My "algorithm" uses BFS in the following way: first the graph is partitioned in levels. The nodes of each level need only 1 step (second) to be reached from the previous one, but every other level has the edges reversed. So the robot starts from the root that has the initial edges, then the nodes that are directly accessible from the root have reversed edges towards the nodes that are closer to the destination etc etc. The robots calculates at every level, if there is a path that starts from the current node to the destination node. If there is, it moves to the next node in that path, since this step is the best one. If not, then it waits for 1 second for the edges to be reversed (final_time++) and then moves to that node.

I am pretty sure that my algorithm is not great and I am not sure if it would work. Also, I am thinking that I would need some type of backtracking in case it reaches a node from which the destination is unreachable.

Any comments or tips on how to construct a better solution? I am not asking for the solution, but for corrections and possibly some hints that will make me find/fix the algorithm. Sorry if some points are not very well explained, English isn't my mother tongue. I am happy to clarify if something is not clear enough.

$\endgroup$

1 Answer 1

2
$\begingroup$

Here's a hint: explicitly create the "mirror graph", and then you redirect all the edges so that the destination is in the other graph. Also, add the edges $vv'$ (and vice versa) where $v'$ is the mirror vertex of $v$.

Now you only need to do a BFS from $s$ to $\{t, t'\}$.

$\endgroup$
6
  • $\begingroup$ If I understand correctly, I will have the starting node and two graphs: G and G_reversed. I will add edges from u (node in G) to u' (same node in G_reversed), and then I will run BFS to the destination nodes(t and t'). That seems like a really good step to the solution and in fact I think it does solve it. BFS will find the path, and every time I go from u to u', it will "take" 1 second, just like waiting for 1 second for the graph to reverse again and then proceed from the reversed node. Thank you so much! $\endgroup$
    – Greggs
    Commented May 2 at 12:43
  • 1
    $\begingroup$ @Greggs I'm not sure if you got the interpretation completely correct. As the OP says, you need to "reroute" each edge. That is, you have two copies of each node, say $v_{even}$ and $v_{odd}$, where the "even" nodes signify an even timestep and vice versa. So, for each directed edge $(u,v)$ in the original graph, you have two edges $(u_{even},v_{odd})$ and $(v_{odd},u_{even})$. In addition to the edges $(v_{even},v_{odd})$ and $(v_{even},v_{odd})$ for each $v$. This way you ensure that you must follow the correct direction of the edges at each timestep. $\endgroup$
    – Highheath
    Commented May 2 at 19:09
  • 2
    $\begingroup$ Another way to describe Pål GD's graph: Create a graph with V' = V x {true, false}. (The boolean is true for verteces in the original graph and false for ones in the mirror graph.) For every directed edge (u, v) in the original graph, add bidirectional edge ((u, true), (v, false)). For each vertex v in original graph, add bidirectional edge ((v, true), (v, false)). Start vertex is (start_orig, true). $\endgroup$ Commented May 2 at 20:28
  • $\begingroup$ Good point. You may just look at it as an undirected graph. $\endgroup$
    – Highheath
    Commented May 2 at 21:27
  • $\begingroup$ @Highheath I see, I missed the part where there are edges between u and v' (from G to G' but different nodes). That way, in each step it will either move from G to G' for different nodes which doesn't cost time for waiting, or move to the mirrored node, and spend one second waiting for the graph to reverse (G->G_rev or G_rev->G). I think that's what you mean, right? $\endgroup$
    – Greggs
    Commented May 3 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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