Hi, I am had sime difficulties using the johnson_all_pairs_shortest_path algorithm. I have a custom weight type called CostType. I tried calling the algorithm as follows.
johnson_all_pairs_shortest_paths(g, D, distance_inf(CostType::infinity()));
The result was a distance matrix with all zeros. The problem is the following lines from johnson_all_pairs_shortest_path.hpp
DT inf = (std::numeric_limits<DT>::max)(); for (tie(v, v_end) = vertices(g2); v != v_end; ++v) d[*v] = inf;
If I specialized the numerical-limits class for CostType everything started to work as expected.
namespace std { template<> class numeric_limits<CostType> { public: inline static CostType min() throw() { return -CostType::infinity();} inline static CostType max() throw() { return CostType::infinity(); } }; }
Even if this is the good way to solve the problem, it doesn't work for what I want to do. I'm trying to calculate the longest paths by redefining distance_inf and distance_compare.
Is this a bug or is it something I don't understand? I am using boost 1.33.1
Another problem is that a user define CombineFunction passed to the distance_combine parameter isn't used. A closed_plus<DT> functor is passed to the bellman_ford_shortest_paths algorithm. Same goes for the compare function. std::less<DT> is used. It seems that the algorithms are not as generic as the documentation makes you believe. When browsing the CVS-repositories I found some references to longest paths algorithms in some of the commit messages: "Make relax work when we're searching for longest paths" Thanks, Peter