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