找出每个节点到 k 个最近特殊节点的距离。

Question

如果我的问题表述不清楚，请告诉我，我会尽力重新表述！

我们有一个大的道路网络（>1,000,000个节点，>3,000,000条边），这个图是无权重和无向的。在这个图中，我们将随机选择1000个节点作为“警察局”。

为了找到从每个节点到最近警察局的距离，我通过实现多源BFS算法解决了这个问题，在开始时将警察局节点添加到队列中。复杂度为O（V+E），而普通BFS运行V次的复杂度为O（V（V+E））。

然而，我想不到一种修改此算法以查找从每个节点到K个最近警察局的距离的方法，而不仅仅是最近的一个。

如果您能建议适当的算法或指导方向，我将非常感激！

- Lee Jun Wei

Answer 1

我们可以从每个警察局作为源头运行BFS P次。 我们可以为每个顶点维护一个大小为k的堆，以维护该顶点与k个最近警局之间的距离。

时间复杂度为O(P(V+E) + PVlogK)。

为了使其更快，我们可以并行运行P个BFS，大大缩短时间，缩短的倍数取决于机器中的处理器核心数量C。

另一个优化是将一个顶点与所有警察局之间的距离存储在列表中，而不是堆中。 然后我们可以使用计数排序并获取最接近的k个站。 这部分的复杂度将从O(VPlogK)变为O(VP)。

- Anmol Singh Jaggi

---

不理解 VKlogP 的原因。假设您使用的是最大堆，并且建立它需要O(k)，那么在最坏的情况下，对P次进行堆化将会花费O（PlogK），因此它不应该是 O(K + PlogK) 吗？ - Siddharth Kamaria

@Siddharth 是的，你说得对。谢谢指出。已经更正了。 - Anmol Singh Jaggi

@LeeJunWei 你说得对。我们最初并没有从数组中构建任何堆。抱歉让你感到困惑。我想我在计算复杂度时有点笨拙了。我会更新答案的。 - Anmol Singh Jaggi

Answer 2

调整算法使其在找到最近的警察局后继续执行。

例如: 将警察局添加到列表中并继续。将其视为普通节点处理。仅在找到K个警察局时停止。

查看Wikipedia上的BFS，我们可以找到以下通用算法：

 1  procedure BFS(G, root) is
 2      let Q be a queue
 3      label root as discovered
 4      Q.enqueue(root)
 5      while Q is not empty do
 6          v := Q.dequeue()
 7          if v is the goal then
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as discovered then
11                  label w as discovered
12                  Q.enqueue(w)

为了让我们能够搜索警察局，我们需要添加以下步骤：

1. 在第3行之后: 除了要用一个队列和集合（当然还有其他方式，例如：布尔型数组来存储编号的节点）保存已发现的节点外，我们需要一个集合来存储已发现的警察局。
2. 删除第7行和第8行。我们不再追求一个特定的节点作为目标。
3. 在第10行之后添加: 如果w是一个警察局，则添加到“已发现的警察局集合”中。如果“已发现的警察局集合”的新大小是K，则返回“已发现的警察局集合”。

哦对了，你需要距离信息，所以当将警察局添加到已发现集合中时，也需要将该距离添加到警察局距离列表中（这也是您需要在算法开头添加的数组）。

- Nuclearman

---

嗯，你可以在那里做一些改进，但是要找到一个更快几倍的更好的选项，可能最好的选择只是 O(P(V + E))，从警察局开始相同的想法。然后对于每个节点，在找到每个警察局到每个节点的距离之后，找到最近的K个警察局。这种方法理论上比我的答案快3000倍（尽管仍然可能比您现在拥有的慢1000倍）。嗯等一下。 - Nuclearman

嗯，我在想我们可以尝试一下超图。基本上是将节点合并。例如：如果B、C、D每个只有2条边，则可以将这些顶点和边折叠成具有权重的单个A-E边，该权重为折叠边的总和。这可能用于减少工作量，但不清楚具体可以减少多少。我认为你无法避免使用上述两种算法之一，但是可以避免多次执行相同的距离计算和沿着相同路径多次执行。我想，折叠2条边的路径会有很大帮助。 - Nuclearman