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;