Am 24.10.18 um 07:21 schrieb altunkayao@itu.edu.tr:
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 <tiago@skewed.de>