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

user_3910428 0
Viewed 492

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!

shortest-path breadth-first-search graph algorithm
2 Answers

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).

user_19253880

Adjust the algorithm so it continues after finding the nearest police station.

IE: Add the police station to a list and continue. Treat it as if it was a normal node. Only stop when you have found K police stations.

Looking at Wikipedia for BFS we find this general algorithm:

 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)

To allow us to search for police stations we just need to add some steps:

  1. After line 3: Along with a Queue, and a Set (though there are other ways, IE: boolean array for numbered nodes) to store discovered nodes, we need a set to store discovered police stations.
  2. Remove lines 7 and 8. We no longer have a specific goal we are seeking in terms of a node.
  3. Add after line 10: If w is a police station, then add to police station discovered set. If the new size of the police stations discovered set is K, return the police stations discovered set.

Oh right, you need the distances, so when adding a police station to the discovered set, also add the distance to the list of police station distances (which is an array you'll have to add at the start of the algorithm too).

user_16082260
Related