根据 OP 的说明，通过将 Dijkstra 的最短路径算法应用于原始图的两个副本的乘积的自然子图，给出了一个精确的解决方案。

让$V$是有序对$(u,v)$的原始节点“彼此相距至少$k$”。假设所需代理路径的两个端点$(a,c)$和$(b,d)$属于$V$.

定义边缘$V$因为两对的一个坐标完全相同，而另一个坐标是由原始图的边连接的节点。也就是说，如果$v$和$w$是原始图中的连接节点，对于任何$u$不小于$k$远离两者$v$和$w$，然后的边缘$V$连接$(u,v)$到$(u,w)$也是一个边缘$V$连接$(v,u)$到$(w,u)$.

正如已经澄清的那样，一个代理在另一个代理移动的每一步“等待”，它仍然只需要注意从$(a,c)$到$(b,d)$在$V$只是两个代理的路径长度之和。因此最短路径在$V$对应于我们希望最小化的这个数量。

我不知道任何确切的算法，但我看到至少有两种近似最优解的方法：

• 计算最短路径$a->b$和$c->d$使用任何现有算法（例如，Dijkstra 算法）。然后模拟两条路径，如果在某一步骤中两个代理太靠近，请执行以下操作之一： (i) 绕道一：例如，如果代理 A 在顶点$v$并且在$v'$之前，然后替换步骤$v'->v$经过$v'->v''->v'$如果可以与代理 B 的位置的距离最大，但与和距离均为 1 。(ii) 如果不存在与则只需在位置再停留一个时间步长。$v''$$v$$v'$$v''$$v,v'$$v'$

• 在图中找到一条按此顺序和之间的距离至少为所需的间距。两个代理沿着这条公共路径遍历图。$a,c,b,d$$a$$c$$k$

我最好的猜测是，如果考虑中的顶点彼此“接近”（相对于），那么第二种算法会更好。否则，第一个算法将产生更好的路径。两种方法都发现它们的结果与最短路径查找算法具有相同的复杂性。$k$