Find the distance from each node to the k-nearest special nodes

Question

Please let me know if my question isn't phrased clearly and I'll try my best to rephrase!

We are given a large road-network (>1,000,000 nodes, >3,000,000 edges), this graph is unweighted and undirected. In this graph, we will select 1000 random nodes as 'police stations'.

To find the distance to the nearest police station from each node, I was able to solve it by implementing a multi-source BFS, where the police station nodes are added to the queue at the start. The complexity is then O(V+E) compared to O(V(V+E)) when running the normal BFS V times.

However, I can't think of a way to modify this algorithm to find the distance to the k-nearest police stations from each node, instead of just the nearest one.

I'd really really appreciate if you guys could suggest a suitable algorithm or point me in the right direction!

Answer 1

We can run BFS P times, once from every police station as the source. We can maintain a heap of size k for every vertex to maintain the k closest police station distances from that vertex.

The time complexity will be O(P(V+E) + PVlogK).

To make it even more faster, we can run the P BFS in parallel to greatly reduce the time by as much as C times where C is the number of processor cores in the machine.

Another optimization is to store the distances between a vertex and all the police stations in a list rather than a heap. We can then use count sort and get the closest k stations. The complexity of this part will change to O(VP) from O(VPlogK).