On 05.03.2015 15:11, François wrote:
My question is: "What happens when the *max_dist* parameter is specified ?"
It does not really change the (worst-time) complexity per se, but it should run faster, since the search is stopped sooner. If max_dist is much smaller than typical distances, it can indeed be much faster.
I observed that the execution time of *shortest_distance* increases linearly with the number of vertices. The execution time goes from 19ms with a sub-sample of 1M vertices and 2M edges to 320ms with the full graph. How can it be explained ?
With only two points it is not possible to distinguish between O(V), O(V log V), O(V ^ 2) or anything else.