Nore wrote:Hmmmm, that is a good question. I'm not sure we can even get something even remotely as good with dynamic shortest paths compared to dynamic connectivity; the problem seems much harder. There seems to be no polylogarithmic algorithm, unfortunately...

Pre-calculating the shortest path (or doing so on the fly) would be an intensive cpu-bound operation and depending on the path-finding algorithm would be done in polynomial time: O(n^2) or greater (way too slow).

I personally think the problem would be more approachable and manageable by treating it as an OO (object-oriented) problem; something is passed into a node and this node is responsible for sending it onto the next node such that the passage from one node to next would eventually narrow-down to the ultimate destination.

If the shortest path is still needed at that point, then the algorithm for selecting the next-best node is greatly simplified.