<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.