1.1 --- a/lemon/floyd_warshall.h	Fri Oct 14 10:53:35 2005 +0000
     1.2 +++ b/lemon/floyd_warshall.h	Fri Oct 14 10:53:51 2005 +0000
     1.3 @@ -27,6 +27,7 @@
     1.4  #include <lemon/graph_utils.h>
     1.5  #include <lemon/invalid.h>
     1.6  #include <lemon/error.h>
     1.7 +#include <lemon/matrix_maps.h>
     1.8  #include <lemon/maps.h>
     1.9  
    1.10  #include <limits>
    1.11 @@ -105,14 +106,14 @@
    1.12      /// \see FloydWarshallDefaultOperationTraits
    1.13      typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits;
    1.14   
    1.15 -    /// \brief The type of the map that stores the last edges of the 
    1.16 +    /// \brief The type of the matrix map that stores the last edges of the 
    1.17      /// shortest paths.
    1.18      /// 
    1.19 -    /// The type of the map that stores the last
    1.20 -    /// edges of the shortest paths.
    1.21 +    /// The type of the map that stores the last edges of the shortest paths.
    1.22      /// It must be a matrix map with \c Graph::Edge value type.
    1.23      ///
    1.24 -    typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
    1.25 +    typedef DynamicMatrixMap<Graph, typename Graph::Node, 
    1.26 +			     typename Graph::Edge> PredMap;
    1.27  
    1.28      /// \brief Instantiates a PredMap.
    1.29      /// 
    1.30 @@ -126,9 +127,9 @@
    1.31      /// \brief The type of the map that stores the dists of the nodes.
    1.32      ///
    1.33      /// The type of the map that stores the dists of the nodes.
    1.34 -    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
    1.35 +    /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
    1.36      ///
    1.37 -    typedef NodeMatrixMap<Graph, Value> DistMap;
    1.38 +    typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
    1.39  
    1.40      /// \brief Instantiates a DistMap.
    1.41      ///
    1.42 @@ -149,6 +150,15 @@
    1.43    /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
    1.44    /// kind of length.
    1.45    ///
    1.46 +  /// The algorithm solves the shortest path problem for each pairs
    1.47 +  /// of node when the edges can have negative length but the graph should
    1.48 +  /// not contain circle with negative sum of length. If we can assume
    1.49 +  /// that all edge is non-negative in the graph then the dijkstra algorithm
    1.50 +  /// should be used from each node rather and if the graph is sparse and
    1.51 +  /// there are negative circles then the johson algorithm.
    1.52 +  ///
    1.53 +  /// The complexity of this algorithm is O(n^3 + e).
    1.54 +  ///
    1.55    /// The type of the length is determined by the
    1.56    /// \ref concept::ReadMap::Value "Value" of the length map.
    1.57    ///