Re: [graph-tool] Shortest_distance complexity when used with max_dist

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.

Best, Tiago