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?<br> - Bhaskara<br><br><br><br>Version 1: with dijkstra_shortest_paths<br><br>ReachableCostVector GridGraph::singleSourceCosts (const Cell2D& source, const vector<Cell2D>& dests)<br>{<br>� GridDistances distances;<br> � GridGraphVertex start = cellVertex(source);<br><br><br>� resetIndices();<br><br>� typedef map<GridGraphVertex, GridGraphVertex> GridPreds;<br>� GridPreds predecessors;<br>� boost::dijkstra_shortest_paths (graph_, start,<br> ��������������������������������� weight_map(get(&EdgeCost::cost, graph_)).<br>��������������������������������� vertex_index_map(get(&CellInfo::index, graph_)).<br>��������������������������������� distance_map(associative_property_map<GridDistances>(distances)).<br> ��������������������������������� predecessor_map(associative_property_map<GridPreds>(predecessors)). // to avoid warnings<br>��������������������������������� visitor(GraphSearchVisitor()));<br><br>�� <br>� ReachableCostVector v(dests.size());<br> � transform (dests.begin(), dests.end(), v.begin(), bind(extractCost, this, distances, _1));<br>� return v;<br>}<br><br><br><br><br>Version 2: without dijkstra_shortest_paths<br><br><br>// Approximation to Dijkstra<br>ReachableCostVector GridGraph::singleSourceCosts (const Cell2D& source, const vector<Cell2D>& dests)<br> {<br>� GridDistances distances;<br>� GridGraphVertex start = cellVertex(source);<br>� typedef pair<GridGraphVertex, double> QueueItem;<br>� queue<QueueItem> q;<br>� set<GridGraphVertex> visited;<br>� <br> � q.push(QueueItem(start,0.0));<br>� visited.insert(start);<br>� while (!q.empty()) {<br>��� <br>��� GridGraphVertex v;<br>��� double d;<br>��� tie(v,d) = q.front();<br>��� q.pop();<br><br>��� GridGraphAdjacencyIterator iter, end;<br> ��� for (tie(iter,end)=adjacent_vertices(v, graph_); iter!=end; iter++) {<br>����� if (visited.find(*iter)==visited.end()) {<br>������� double cost = d+graph_[edge(v,*iter,graph_).first].cost;<br>������� q.push(QueueItem(*iter, cost));<br> ������� visited.insert(*iter);<br>������� distances[*iter] = cost;<br>����� }<br>��� }<br>� }<br>� ReachableCostVector costs;<br>� for (vector<Cell2D>::const_iterator iter=dests.begin(); iter!=dests.end(); ++iter) {<br> ��� GridDistances::iterator pos = distances.find(cellVertex(*iter));<br>��� if (pos==distances.end()) <br>����� costs.push_back(ReachableCost(false,-42.0));<br>��� else<br>����� costs.push_back(ReachableCost(true, pos->second));<br> � }<br>� return costs;<br>}<br><br>