diff -r 2acb5f9bfa72 -r fb4f801dd692 lemon/floyd_warshall.h
--- a/lemon/floyd_warshall.h	Fri Oct 14 10:53:35 2005 +0000
+++ b/lemon/floyd_warshall.h	Fri Oct 14 10:53:51 2005 +0000
@@ -27,6 +27,7 @@
 #include <lemon/graph_utils.h>
 #include <lemon/invalid.h>
 #include <lemon/error.h>
+#include <lemon/matrix_maps.h>
 #include <lemon/maps.h>
 
 #include <limits>
@@ -105,14 +106,14 @@
     /// \see FloydWarshallDefaultOperationTraits
     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.
     /// 
@@ -126,9 +127,9 @@
     /// \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.
+    /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
     ///
-    typedef NodeMatrixMap<Graph, Value> DistMap;
+    typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
 
     /// \brief Instantiates a DistMap.
     ///
@@ -149,6 +150,15 @@
   /// \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
   /// \ref concept::ReadMap::Value "Value" of the length map.
   ///