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.

Unfortunately for same case I need to implement a graph with time-dependent
weights (e.g. Time Dependent Dijkstra (TDD)), therefore I have to customize
the dijkstra search.

In case I would like to write a c++ extension, which steps do you suggest me
to take?
I saw that you use dijkstra_shortest_paths_no_color_map_no_init from boost
library with the class djk_max_visitor. Do you think I can just extend the
class adding the examine_edge method?

I saw that you use dijkstra_shortest_paths_no_color_map_no_init from boost
library with the class djk_max_visitor. Do you think I can just extend the
class adding the examine_edge method?