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&amp; source, const vector&lt;Cell2D&gt;&amp; dests)<br>{<br>� GridDistances distances;<br>
� GridGraphVertex start = cellVertex(source);<br><br><br>� resetIndices();<br><br>� typedef map&lt;GridGraphVertex, GridGraphVertex&gt; GridPreds;<br>� GridPreds predecessors;<br>� boost::dijkstra_shortest_paths (graph_, start,<br>
��������������������������������� weight_map(get(&amp;EdgeCost::cost, graph_)).<br>��������������������������������� vertex_index_map(get(&amp;CellInfo::index, graph_)).<br>��������������������������������� distance_map(associative_property_map&lt;GridDistances&gt;(distances)).<br>
��������������������������������� predecessor_map(associative_property_map&lt;GridPreds&gt;(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&amp; source, const vector&lt;Cell2D&gt;&amp; dests)<br>
{<br>� GridDistances distances;<br>� GridGraphVertex start = cellVertex(source);<br>� typedef pair&lt;GridGraphVertex, double&gt; QueueItem;<br>� queue&lt;QueueItem&gt; q;<br>� set&lt;GridGraphVertex&gt; 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&lt;Cell2D&gt;::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-&gt;second));<br>
� }<br>� return costs;<br>}<br><br>