<disclaimer> I hope this question isn't too dumb, if it is please accept my apologies. </disclaimer> Hi list, The graph that I work with has ≈ 30M vertices and ≈ 60M edges. This graph has positive weights, it represents a Road network. I need to compute the shortest path form a node to any other node within a range. The documentation shortest_distance <http://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.shortest_distance> , states that the complexity (source and weights specified) is O(VlogV). My question is: "What happens when the *max_dist* parameter is specified ?" 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 ? Thanks for your help, François. -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.