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

Question

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

我们有一个大型道路网络（>1,000,000 个节点，>3,000,000 条边），此图未加权且无向。在此图中，我们将 select 1000 个随机节点作为 'police stations'.

为了找到从每个节点到最近的警察局的距离，我能够通过实现多源 BFS 来解决这个问题，其中警察局节点被添加到开始时的队列。当 运行 正常 BFS V 倍时，复杂度为 O(V+E) 与 O(V(V+E)) 相比。

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

如果你们能提出合适的算法或为我指明正确的方向，我将不胜感激！

Answer 1

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

IE：将警察局添加到列表中并继续。将其视为普通节点。找到K个派出所才停下来

查看 Wikipedia for 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 行之后：除了一个 Queue 和一个 Set（尽管还有其他方法，IE：用于编号节点的布尔数组）来存储已发现的节点，我们还需要一个 set 来存储已发现的警察局。
2. 删除第 7 行和第 8 行。我们不再有我们在节点方面寻求的特定目标。
3. 在第10行后添加：如果w是派出所，则添加到police station discovered set。如果police stations discovered set的新尺寸是K，return则police stations discovered set。

哦，对了，你需要距离，所以在将警察局添加到发现集时，还要将距离添加到警察局距离列表（这是一个数组，你必须在算法也是）。

Answer 2

我们可以运行BFS P次，以每个派出所一次为源。 我们可以为每个顶点维护一个大小为 k 的堆，以维护距该顶点的 k 个最近的警察局距离。

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

为了让它更快，我们可以 运行 并行 P BFS 将时间大大减少 C 倍，其中 C 是机器中处理器核心的数量。

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