algorithm - 求每个节点到 k-nearest 特殊节点的距离

Question

如果我的问题没有表述清楚，请告诉我，我会尽力改写!
给定一个大型道路网络(> 1,000,000 个节点，> 3,000,000 条边)，该图未加权且无向。在此图中，我们将选择 1000 个随机节点作为“警察局”。
查找到最近警察局的距离 来自每个节点 ，我能够通过实现多源BFS来解决它，其中警察局节点在开始时添加到队列中。与运行正常 BFS V 次时的 O(V(V+E)) 相比，复杂性是 O(V+E)。
但是，我想不出一种方法来修改这个算法来找到每个节点到 k 最近警察局的距离，而不仅仅是最近的一个。
如果你们能提出合适的算法或指出我正确的方向，我真的很感激!

Answer 1

我们可以运行 BFS P 次，每次从每个派出所作为源。
我们可以为每个顶点维护一个大小为 k 的堆，以保持与该顶点最近的 k 个警察局距离。
时间复杂度为 O(P(V+E) + PVlogK)。
为了让它更快，我们可以并行运行 P BFS 以将时间大大减少 C 倍，其中 C 是机器中处理器内核的数量。
另一个优化是将顶点与所有警察局之间的距离存储在列表中而不是堆中。
然后我们可以使用计数排序并获得最近的 k 个站点。
这部分的复杂度将从 O(VPlogK) 变为 O(VP)。