[boost] Priority Queue in boost::graph::dijkstra_shortest_paths

From: Lloyd J Lewins (llewins_at_[hidden])
Date: 2005-02-21 13:00:08

Perhaps I am missing something, but I don't see how 
dijkstra_shortest_paths works currently.

The priority queue (mutable_queue) in dijkstra_shortest_paths should order 
(gray) vertices by their distance from the source vertex. The ordering of 
the mutable_queue is achieved by the compare function, which therefore 
should order vertices by examining the distance map. However, the default 
compare function is simply std::less<D>(), where D is the value_type of 
the distance map. I.e., the compare simply orders the vertices by their 
vertex_descriptor, using less for the value_type (essentially a cast). I 
would think what is really needed is a less function which is bound to the 
distance map, and compares based off distance. For example:

    template<class Map>
    class less : public std::binary_function<typename 
boost::property_traits<Map>::value_type, 
                                              typename 
boost::property_traits<Map>::value_type, bool>
    {
        typedef typename boost::property_traits<Map>::key_type   key_type;
        typedef typename boost::property_traits<Map>::value_type 
value_type;

    public:
        explicit less(Map& m)
            : m(m)
        {
        }
 
        bool operator() (const key_type k1,
                         const key_type k2) const
        {
            return m[k1] < m[k2];
        }
 
    private:
        const Map& m;
    };
 
In which case the compare function would be somethink like: 
less<DistanceMap>(distance).

Lloyd J. Lewins
Fellow,
Raytheon Co.,
llewins_at_[hidden]
[phone]