[graph-tool] Performance search vs shortest_path

Tiago de Paula Peixoto tiago at skewed.de
Tue Feb 9 09:15:10 CET 2021


Am 08.02.21 um 20:10 schrieb Alessandro Tonin:
> First of all, thanks a lot for this amazing library.
> 
> I have a question about the performance of shortest_path vs dijkstra_search
> with a custom Visitor.
> 
> I implemented a very  basic example
> <https://nabble.skewed.de/file/t496286/basic_example.py>   with a Visitor
> with just the method
> 
> 
> Using a graph of approx. 60k edges and 60k vertices, the performance of
> dijkstra_search are 30 times slower than the default method shortest_path.
> 
> 
> Is this difference normal, or I am doing some error in the code?

This is perfectly normal.

The function dijkstra_search() involves the Python interpreter when 
invoking your visitor object, but shortest_path() is implemented purely 
in C++. This is where the speed difference comes from.

dijkstra_search() is there when you want to customize somehow the search 
(see also dijkstra_iterator()). But if you only want to compute shortest 
paths or distances, then you should use the specialized functions.

Best,
Tiago

-- 
Tiago de Paula Peixoto <tiago at skewed.de>


More information about the graph-tool mailing list