Boost::graph Dijkstra : initially populating the queue

4
votes

I'm using boost::graph and its Dijkstra implementation.

I want to compute THE shortest path from a set of vertices to another set of vertices. I do not want to compute all the possible paths between those sets.

The idea is the following : I'm in a building with entrances on various streets. So I can start my journey on any of those streets. But I'm only interested in the shortest one.

If I had used my own implementation of Dijkstra's algorithm, I would have done the following:

  • For each start node, the distance map to 0
  • Add the start node to the priority queue.

While it's easy to set the distance map to 0 using boost::dijkstra_shortest_paths_no_init, I cannot figure out how to add the node to the priority queue. I looked into the source code, and it seems pretty much impossible. So I'm thinking of defining my own Combine functor that will return a 0 distance if I reach one of the start nodes, but it seems rather ugly.

I could create a virtual node, and add edges from the virtual node to starting nodes. However, this triggers some concurrent access problems I would like to avoid.

Did I miss a possibility in the boost library, or does someone know of a clever workaround. I'm also thinking of patching boost to allow a custom initialization of the priority queue.

1
c++algorithmdijkstraboost-graph
None of the major "shortest path" algorithms compute "all the possible paths" They compute only a shortest path. Dijkstra's algorithm has to compute a shortest path from a single node to every-other node in a graph as part of its nature. It's not doing any extra work. - David Nehme
And I do not want to compute all the possible paths (but algorithms exist like Floyd–Warshall's). There is nothing wrong with stuffing the priority queue with multiple departure points; the behaviour is the same as if you had null cost edges from your virtual to the starting nodes) - Tristram Gräbener
Floyd–Warshal's doesn't compute "all possible paths". It computes a shortest path for all-pairs of nodes. - David Nehme

1 Answers

1
votes

I've not used boost::graph, and I hope somebody with better knowledge of it will give a better answer, but perhaps you could create a graph type that wraps the existing graph, leaving the original unmodified, but exposing to the algorithm a view that includes your virtual nodes and edges? If not, is it infeasible to copy the whole graph?