<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/Shortest-distance-complexity-when-used-with-max-dist-tp4026018.html Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com. _______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
