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?
Perhaps the code below doesn't compute the shortest paths? if the "queue" in the code below refers to std::queue, it won't be a priority queue, but a first in first out queue. The priority queue would be std::priority_queue. The important question is not whether the code below has this specific bug, but whether it gives the same answer as dijkstra_shortest_paths for the input data where you observed dijkstra_shortest_paths to be running very slowly (and still being a couple of orders magnitude faster). In that case, it would really be interesting to find out why dijkstra_shortest_paths would be slower that the code below. Regards, Thomas