<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.sh…>
, 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.
