[Boost-commit] svn:boost r48611 - trunk/boost/graph

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;