I encountered a similar problem in a very different situation a few years ago: I had to route video streams across a network of nodes connected by point-to-point connections.
At first I thought I would apply a pathfinding algorithm like A* to route each stream but given that it was an arbitrary graph and not a 2D map there was no obvious heuristic to guide the algorithm, so it devolved into an exhaustive search.
But then I realized that I had relatively few nodes (a dozen at most) and many more streams to route, so it made more sense to compute the distance between every pair of nodes once (n^2 with the number of nodes using a trivial implementation, less if you optimize it but I didn't even need to) and then I could lookup the path between any two nodes in linear time. Given that this was all running on an underpowered embedded system it made a significant difference in performance when routing hundreds of streams.
I'm not very good at big-O. I meant that in order to build the path I would need to lookup the neighboring nodes to find the closest to the target, then just to that node and continue until the end. So it's linear with the average distance I guess.
Yeah, linear with regards to the number of nodes - double the amount of nodes and you'll need to do double the look-ups; and constant with regards to the number of streams - no matter how many streams, always the same number of look-ups.
At first I thought I would apply a pathfinding algorithm like A* to route each stream but given that it was an arbitrary graph and not a 2D map there was no obvious heuristic to guide the algorithm, so it devolved into an exhaustive search.
But then I realized that I had relatively few nodes (a dozen at most) and many more streams to route, so it made more sense to compute the distance between every pair of nodes once (n^2 with the number of nodes using a trivial implementation, less if you optimize it but I didn't even need to) and then I could lookup the path between any two nodes in linear time. Given that this was all running on an underpowered embedded system it made a significant difference in performance when routing hundreds of streams.