Changeset 1723:fb4f801dd692 in lemon-0.x

Timestamp:

10/14/05 12:53:51 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Really short description of these shortest path algorithms

Location:

lemon

Files:

• belmann_ford.h (modified) (3 diffs)
• floyd_warshall.h (modified) (4 diffs)
• johnson.h (modified) (4 diffs)

lemon/belmann_ford.h

@@ -145 +145 @@
   ///
   /// \ingroup flowalgs
-  /// This class provides an efficient implementation of \c BelmannFord 
+  /// This class provides an efficient implementation of \c Belmann-Ford 
   /// algorithm. The edge lengths are passed to the algorithm using a
   /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
   /// kind of length.
+  ///
+  /// The Belmann-Ford algorithm solves the shortest path from one node
+  /// problem when the edges can have negative length but the graph should
+  /// not contain circle with negative sum of length. If we can assume
+  /// that all edge is non-negative in the graph then the dijkstra algorithm
+  /// should be used rather.
+  ///
+  /// The complexity of the algorithm is O(n * e).
   ///
   /// The type of the length is determined by the
@@ -403 +411 @@
     /// - The distance of each node from the root(s).
     void start() {
-      bool ready = false;
-      while (!ready) {
-        ready = true;
+      int num = countNodes(*graph) - 1;
+      for (int i = 0; i < num; ++i) {
+        bool ready = true;
         for (EdgeIt it(*graph); it != INVALID; ++it) {
           Node source = graph->source(it);
@@ -417 +425 @@
           }
         }
-      }
+        if (ready) return;
+      }
+    }
+
+    /// \brief Executes the algorithm and check the negative circles.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function. If there is
+    /// a negative circle in the graph it gives back false.
+    ///
+    /// This method runs the %BelmannFord algorithm from the root node(s)
+    /// in order to compute the shortest path to each node. The algorithm 
+    /// computes 
+    /// - The shortest path tree.
+    /// - The distance of each node from the root(s).
+    bool checkedStart() {
+      int num = countNodes(*graph);
+      for (int i = 0; i < num; ++i) {
+        bool ready = true;
+        for (EdgeIt it(*graph); it != INVALID; ++it) {
+          Node source = graph->source(it);
+          Node target = graph->target(it);
+          Value relaxed = 
+            OperationTraits::plus((*_dist)[source], (*length)[it]);
+          if (OperationTraits::less(relaxed, (*_dist)[target])) {
+            _pred->set(target, it);
+            _dist->set(target, relaxed);
+            ready = false; 
+          }
+        }
+        if (ready) return true;
+      }
+      return false;
     }
     

lemon/floyd_warshall.h

@@ -28 +28 @@
 #include <lemon/invalid.h>
 #include <lemon/error.h>
+#include <lemon/matrix_maps.h>
 #include <lemon/maps.h>
 
@@ -106 +107 @@
     typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits;
  
-    /// \brief The type of the map that stores the last edges of the 
+    /// \brief The type of the matrix map that stores the last edges of the 
     /// shortest paths.
     /// 
-    /// The type of the map that stores the last
-    /// edges of the shortest paths.
+    /// The type of the map that stores the last edges of the shortest paths.
     /// It must be a matrix map with \c Graph::Edge value type.
     ///
-    typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
+    typedef DynamicMatrixMap<Graph, typename Graph::Node, 
+                             typename Graph::Edge> PredMap;
 
     /// \brief Instantiates a PredMap.
@@ -127 +128 @@
     ///
     /// The type of the map that stores the dists of the nodes.
-    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
-    ///
-    typedef NodeMatrixMap<Graph, Value> DistMap;
+    /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
+    ///
+    typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
 
     /// \brief Instantiates a DistMap.
@@ -149 +150 @@
   /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
   /// kind of length.
+  ///
+  /// The algorithm solves the shortest path problem for each pairs
+  /// of node when the edges can have negative length but the graph should
+  /// not contain circle with negative sum of length. If we can assume
+  /// that all edge is non-negative in the graph then the dijkstra algorithm
+  /// should be used from each node rather and if the graph is sparse and
+  /// there are negative circles then the johson algorithm.
+  ///
+  /// The complexity of this algorithm is O(n^3 + e).
   ///
   /// The type of the length is determined by the

lemon/johnson.h

@@ -30 +30 @@
 #include <lemon/error.h>
 #include <lemon/maps.h>
+#include <lemon/matrix_maps.h>
 
 #include <limits>
@@ -107 +108 @@
     typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
  
-    /// \brief The type of the map that stores the last edges of the 
+    /// \brief The type of the matrix map that stores the last edges of the 
     /// shortest paths.
     /// 
-    /// The type of the map that stores the last
-    /// edges of the shortest paths.
+    /// The type of the map that stores the last edges of the shortest paths.
     /// It must be a matrix map with \c Graph::Edge value type.
     ///
-    typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
+    typedef DynamicMatrixMap<Graph, typename Graph::Node, 
+                             typename Graph::Edge> PredMap;
 
     /// \brief Instantiates a PredMap.
@@ -125 +126 @@
     }
 
-    /// \brief The type of the map that stores the dists of the nodes.
-    ///
-    /// The type of the map that stores the dists of the nodes.
-    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
-    ///
-    typedef NodeMatrixMap<Graph, Value> DistMap;
-
+    /// \brief The type of the matrix map that stores the dists of the nodes.
+    ///
+    /// The type of the matrix map that stores the dists of the nodes.
+    /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
+    ///
+    typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
+    
     /// \brief Instantiates a DistMap.
     ///
@@ -150 +151 @@
   /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
   /// kind of length.
+  ///
+  /// The algorithm solves the shortest path problem for each pairs
+  /// of node when the edges can have negative length but the graph should
+  /// not contain circle with negative sum of length. If we can assume
+  /// that all edge is non-negative in the graph then the dijkstra algorithm
+  /// should be used from each node.
+  ///
+  /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
+  /// with fibonacci heap O(n^2 * log(n) + n * e).
   ///
   /// The type of the length is determined by the