0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Aug 10, 2022 at 15:39
  • $\begingroup$ 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 $\endgroup$
    – user12878817821
    Aug 10, 2022 at 16:17
  • $\begingroup$ Are weights non-negative? $\endgroup$
    – D.W. ♦
    Aug 10, 2022 at 19:23

1 Answer 1

Reset to default
0
$\begingroup$

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.

With the addendum, this seems much harder. I would suggest exploring dynamic shortest-paths. See, e.g., Recalculating shortest path after changing the weights, State-of-the-Art techniques on dynamic shortest path computations.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.