performance of dijkstra_shortest_paths

30 Apr 2009

      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;
}

Bhaskara Marthi

Thomas Klimpel

Andrew Sutton

Bhaskara Marthi

Thomas Klimpel

Jeremiah Willcock

Bhaskara Marthi

Bhaskara Marthi

tags

participants (4)