# Algorithms for finding closest graph node within set of nodes

Given a set of nodes $$N$$ on an undirected, weighted graph $$G$$ and a query node $$n$$, what is the fastest algorithm for finding the node in $$N$$ that is closest to $$n$$?

Furthermore, say we are doing many of these queries, so have many $$n$$'s, is there some data structure that could speed up this computation?

Thank you for any feedback or guidance.

Addendum: One other detail I did not mention, every time a query is made, $$n$$ is added to $$N$$, so for the next query, $$N$$ is larger by one node. Is there some version of Dijkstra's or bellman ford that can handle this dynamic situation?

• Do you have any limits/restrictions on the amount of computation done during preprocessing or the amount of space used by the data structure? Should we focus on the case where the number of queries is very large?
– D.W.
Commented Aug 10, 2022 at 15:39
• It is for a graph with 500k nodes and an N of 50k nodes, but no hard restrictions or limits, just something that is tractable would be nice Commented Aug 10, 2022 at 16:17
• Are weights non-negative?
– D.W.
Commented Aug 10, 2022 at 19:23

Without the addendum, you could do $$O(|V|+|E|)$$-time preprocessing (a single BFS, starting from the set $$N$$) that would let you solve each query in $$O(1)$$ time.