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<GridGraphVertex, GridGraphVertex> 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<GridGraphVertex, double> 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;
}