Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r48611 - trunk/boost/graph
From: dgregor_at_[hidden]
Date: 2008-09-05 09:59:12


Author: dgregor
Date: 2008-09-05 09:59:12 EDT (Fri, 05 Sep 2008)
New Revision: 48611
URL: http://svn.boost.org/trac/boost/changeset/48611

Log:
Fix handling of infinite weights in Floyd-Warshall algorithm. Fixes #1700
Text files modified:
   trunk/boost/graph/floyd_warshall_shortest.hpp | 16 ++++++++--------
   1 files changed, 8 insertions(+), 8 deletions(-)

Modified: trunk/boost/graph/floyd_warshall_shortest.hpp
==============================================================================
--- trunk/boost/graph/floyd_warshall_shortest.hpp (original)
+++ trunk/boost/graph/floyd_warshall_shortest.hpp 2008-09-05 09:59:12 EDT (Fri, 05 Sep 2008)
@@ -59,15 +59,15 @@
       
       for (tie(k, lastk) = vertices(g); k != lastk; k++)
         for (tie(i, lasti) = vertices(g); i != lasti; i++)
- for (tie(j, lastj) = vertices(g); j != lastj; j++)
- {
- d[*i][*j] =
- detail::min_with_compare(d[*i][*j],
- combine(d[*i][*k], d[*k][*j]),
- compare);
- }
+ if(d[*i][*k] != inf)
+ for (tie(j, lastj) = vertices(g); j != lastj; j++)
+ if(d[*k][*j] != inf)
+ d[*i][*j] =
+ detail::min_with_compare(d[*i][*j],
+ combine(d[*i][*k], d[*k][*j]),
+ compare);
+
       
-
       for (tie(i, lasti) = vertices(g); i != lasti; i++)
         if (compare(d[*i][*i], zero))
           return false;


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk