I recently ran into a situation where dijkstra_shortest_paths in the boost
graph library was running very slowly. When I replaced the call to
dijkstra_shortest_paths with the code below, things were a couple of orders
magnitude faster. Any idea why?
- Bhaskara
Version 1: with dijkstra_shortest_paths
ReachableCostVector GridGraph::singleSourceCosts (const Cell2D& source,
const vector<Cell2D>& dests)
{
GridDistances distances;
GridGraphVertex start = cellVertex(source);
resetIndices();
typedef map GridPreds;
GridPreds predecessors;
boost::dijkstra_shortest_paths (graph_, start,
weight_map(get(&EdgeCost::cost, graph_)).
vertex_index_map(get(&CellInfo::index,
graph_)).
distance_map(associative_property_map<GridDistances>(distances)).
predecessor_map(associative_property_map<GridPreds>(predecessors)). // to
avoid warnings
visitor(GraphSearchVisitor()));
ReachableCostVector v(dests.size());
transform (dests.begin(), dests.end(), v.begin(), bind(extractCost, this,
distances, _1));
return v;
}
Version 2: without dijkstra_shortest_paths
// Approximation to Dijkstra
ReachableCostVector GridGraph::singleSourceCosts (const Cell2D& source,
const vector<Cell2D>& dests)
{
GridDistances distances;
GridGraphVertex start = cellVertex(source);
typedef pair QueueItem;
queue<QueueItem> q;
set<GridGraphVertex> visited;
q.push(QueueItem(start,0.0));
visited.insert(start);
while (!q.empty()) {
GridGraphVertex v;
double d;
tie(v,d) = q.front();
q.pop();
GridGraphAdjacencyIterator iter, end;
for (tie(iter,end)=adjacent_vertices(v, graph_); iter!=end; iter++) {
if (visited.find(*iter)==visited.end()) {
double cost = d+graph_[edge(v,*iter,graph_).first].cost;
q.push(QueueItem(*iter, cost));
visited.insert(*iter);
distances[*iter] = cost;
}
}
}
ReachableCostVector costs;
for (vector<Cell2D>::const_iterator iter=dests.begin(); iter!=dests.end();
++iter) {
GridDistances::iterator pos = distances.find(cellVertex(*iter));
if (pos==distances.end())
costs.push_back(ReachableCost(false,-42.0));
else
costs.push_back(ReachableCost(true, pos->second));
}
return costs;
}
