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

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.

-
The requirement that "in any time" the paths are at points "away from each other by at least k" needs clarification. It would generally not be the case that both "shortest paths" have the same length, so the agents stepping along the paths would not be able to begin together and end together (unless delay of one agent were allowed). Also is it a requirement that "shortest path" is taken with respect to all paths, or only with respect to the mutual avoidance-by-at-least-k condition? –  hardmath Jan 21 '13 at 14:28

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.

-
I don't know if the algorithm is optimal, but this solution is very elegant! +1 –  Dr_Sam Mar 7 '13 at 12:23

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.

-