
Dear Jeremiah and Boost list, I'd like to suggest for inclusion in Boost Graph Library an algorithm object version of dijkstra shortest path algorithm. The following is an example how it can be used, assuming some graph, source node(s) and threshold distance: auto dijkstra make_dijkstra_object(graph, source_range); while(dijkstra()) { auto v = dijkstra.get_vertex(); auto distance_map = dijkstra.get<vertex_distance_t>(); if(get(distance_map, v) > threshold) break; } It is very close to what Jeremiah suggested 2 years ago: http://lists.boost.org/Archives/boost/2012/07/195300.php The main advantage for me is the possibility to interweave several shortest path searches. The algorithm object makes use of the stackless coroutine in Boost ASIO, which means it is relatively lightweight. However, on a large graph the algorithm object still takes about 20% more time than the normal dijkstra_shortest_path. The operator() progresses the algorithm to the next control point. Control points can correspond to all places where breadth_first_search invokes its visitor, but it is specified in compile time at which potential control points the algorithm actually yields. The default is to halt at the finish_vertex control point only. The make_dijkstra_object function can take all parameters through bgl_named_parameters, including the priority queue and the color map, which the existing dijkstra_shortest_path does not support. The code is part of the following project: http://code.google.com/p/resumable-dijkstra The algorithm object is defined here: http://code.google.com/p/resumable-dijkstra/source/browse/trunk/resumable-di jkstra/blink/graph/dijkstra_object.hpp I look forward to hear if there are any takers this time. Best wishes, Alex