Given a set of nodes $N$ on an undirected, positive 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?
A direct approach seems to pre-run the Bellman-Ford on the entire network, giving all pairs shortest paths for the entire network, or if $|N| \ll |V(G)|$, perhaps, Dijkstra for every $v \in N$. Then you just look up the correct stored structure for each $n$ of interest.
This way, the cost of pre-computation is likely not so important, since typically you are really worried about the cost of actual query every time, as opposed to some (perhaps offline/overnight calculation), and the actual query is just a cheap lookup.