Changeset 1741:7a98fe2ed989 in lemon-0.x for lemon/floyd_warshall.h

Timestamp:

10/26/05 12:50:47 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2269

Message:

Some modifications on shortest path algoritms:

• heap traits
• checked execution

File:

• lemon/floyd_warshall.h (modified) (2 diffs)

lemon/floyd_warshall.h

@@ -393 +393 @@
         for (NodeIt jt(*graph); jt != INVALID; ++jt) {
           _pred->set(it, jt, INVALID);
-          _dist->set(it, jt, it == jt ? 
-                     OperationTraits::zero() : OperationTraits::infinity());
+          _dist->set(it, jt, OperationTraits::infinity());
         }
+        _dist->set(it, it, OperationTraits::zero());
       }
       for (EdgeIt it(*graph); it != INVALID; ++it) {
@@ -427 +427 @@
         }
       }
+    }
+
+    /// \brief Executes the algorithm and checks the negative circles.
+    ///
+    /// This method runs the %FloydWarshall algorithm in order to compute 
+    /// the shortest path to each node pairs. If there is a negative circle 
+    /// in the graph it gives back false. 
+    /// The algorithm computes 
+    /// - The shortest path tree for each node.
+    /// - The distance between each node pairs.
+    bool checkedStart() {
+      start();
+      for (NodeIt it(*graph); it != INVALID; ++it) {
+        if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) {
+          return false;
+        }
+      }
+      return true;
     }