Finding two shortest path that are 'distant' in the graph

Question

The problem is as follows: We are given a graph with each edge length 1 and two pairs of vertices (a,b) and (c,d).

How to find shortest paths between from a to b and from c to d, with assumption that there is a way of moving through both paths (step by step) such that in any time our agents (the one moving from a to b and the other moving from c to d) will be away from each other by at least k?

Edit:

To make it more clear:

• Agents move separately, so in each step only one agent moves and agent can move few times in row (the other 'waits').
• We are looking for such paths that the summed length is minimal.
• Paths are 'valid' if there exists a sequence of agent moves in which at any time agents are at least k distant.

We can assume that the input is nice, so there always exists the pair of paths that meets conditions.

Answer 1

Subject to the OP's clarifications, an exact solution is given by applying Dijkstra's shortest path algorithm to a natural subgraph of a product of two copies of the original graph.

Let $V$ be the ordered pairs $(u,v)$ of original nodes which are "away from each other by at least $k$". By assumption both endpoints of the desired agents' path $(a,c)$ and $(b,d)$ belong to $V$.

Define edges for $V$ as those where two pairs have exactly one coordinate the same and in the other coordinate are nodes connected by an edge of the original graph. That is, if $v$ and $w$ are connected nodes in the original graph, for any $u$ not less than $k$ distant from both $v$ and $w$, then an edge of $V$ connects $(u,v)$ to $(u,w)$ and also an edge of $V$ connects $(v,u)$ to $(w,u)$.

As it was clarified one agent "waits" at each step where the other agent moves, it remains only to note that the length of a path from $(a,c)$ to $(b,d)$ in $V$ is simply the sum of path lengths for both agents. Therefore the shortest path in $V$ corresponds to this quantity which we desired to minimize.

Answer 2

I do not know any exact algorithm but I see at least two approaches to approximate an optimal solution:

• Compute the shortest path $a->b$ and $c->d$ using any of the existing algorithms (e.g., Dijkstra's algorithm). Then simulate the two paths and, if at one step the two agents are too close do one of the following: (i) Detour by one: If agent A is, for example, at vertex $v$ and was at $v'$ before, then replace the step $v'->v$ by $v'->v''->v'$ if you can where $v''$ has maximal distance from the position of agent B at that time but has distance one from both $v$ and $v'$. (ii) If no such $v''$ exists that is neighbor to both $v,v'$, then simply stay at position $v'$ for one more time step.

• Find a path through the graph that includes $a,c,b,d$ in this order. Then add vertices to this cycle so that the distance between $a$ and $c$ along your cycle is at least the desired separation $k$. The two agents traverse the graph along this common path.

My best guess is that if the vertices under consideration are "close" to each other (relative to $k$) then the second algorithm will be better. Otherwise, the first algorithm will produce better paths. Both methods find their result in the same complexity as the shortest path finding algorithm.