Florian G. Pflug wrote:

>
> 3,628,800 is still a lot of traversals... :-(

It surely is, and it's definitely unnecessarily high.

Our "worst case" should be to do a shortest patch calculation from each
origin to each receiver.

Dijkstra's algorithm does that in O(n^2) time, and we would have to do
this for n origins and (n-1) receivers.

Thus, worst case should be O(n^4).

Any alternative that heads into "factorial land" is a worse answer than
doing n(n-1) shortest path problems.

I'm inclined to set up a dynamic programming formulation for the
shortest path problems; that can indeed be expected to run in O(n^2)
time, and, when paths are restricted, it'll do somewhat better than that...