Am 24.10.18 um 07:21 schrieb [email protected]: > > I also wonder if the performance differences between those two graphs are > expected to be much different, i.e., it takes 9 minutes to obtain shortest > path between 400,000 pairs in the normal graph, and it takes > 52 hours for the weighted one. > > Here is how I'm doing it: > > path = [] > for item in pairs: > vpath, epath = gt.shortest_path(weighted_graph, > weighted_graph.vertex(item[0]), > weighted_graph.vertex(item[1]), > weights=weights, > negative_weights=True)
For unweighted graphs the algorithm is BFS which is O(V + E), and for weighted graphs it's Dijkstra, which is O(V log V). However if negative weights are used, the algorithm is Bellman-Ford, which is much slower, with O(V * E). -- Tiago de Paula Peixoto <[email protected]> _______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
