algorithm - 在图中找到距离至少为 D(常数) 的两条路径

Question

问题实例:无向无权图 G=(V,E)。两个源节点a和b，两个目的节点c和d以及一个常数D(完全正数)。(我们可以假设lambda(c,d),lambda(a,b)>D，当lambda(x,y ) 是 G) 中 x 和 y 之间的最短路径。我们有两个人站在节点 a 和 b 上。

定义:调度器集-调度器集是一组命令，使得在每个步骤中只有一个人从他的节点 v 移动到 v 个邻居中的一个，当他们的起始位置在节点 a、b 中并且结束位置在节点 c,d. 如果在每个步骤中两个人之间的距离 > D，则“调度程序集”是 missing-disorders。

我需要找到一种算法来确定是否存在“缺失障碍调度程序集”。

有什么建议吗？

Answer 1

一个简单的解决方案是首先解决 all-pairs shortest paths在 O(n * (n + m)) 中对每个节点使用 n 个广度优先搜索。

然后创建具有 lambda(x, y) > D 的有效节点对 (x,y) 的图，边表示可能的移动。存在边 {(v,w), (x,y)} 如果 v = x 并且在原始图中存在边 {w, y} 或者如果 w = y 并且存在边 {v, x}在原始图中。这个新图有 O(n^2) 个节点和 O(nm) 个边。

现在您只需要检查新图中的 (c, d) 是否可以从 (a, b) 到达。这可以使用 DFS 或 BFS 来实现。

总运行时间为 O(n * (n + m))。