Re: [Boost-users] performance of dijkstra_shortest_paths

Subject: Re: [Boost-users] performance of dijkstra_shortest_paths
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-05-01 05:52:54

> 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