1.1 --- a/lemon/johnson.h	Fri Oct 14 10:53:35 2005 +0000
     1.2 +++ b/lemon/johnson.h	Fri Oct 14 10:53:51 2005 +0000
     1.3 @@ -29,6 +29,7 @@
     1.4  #include <lemon/invalid.h>
     1.5  #include <lemon/error.h>
     1.6  #include <lemon/maps.h>
     1.7 +#include <lemon/matrix_maps.h>
     1.8  
     1.9  #include <limits>
    1.10  
    1.11 @@ -106,14 +107,14 @@
    1.12      /// \see JohnsonDefaultOperationTraits
    1.13      typedef JohnsonDefaultOperationTraits<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 @@ -124,13 +125,13 @@
    1.31        return new PredMap(graph);
    1.32      }
    1.33  
    1.34 -    /// \brief The type of the map that stores the dists of the nodes.
    1.35 +    /// \brief The type of the matrix map that stores the dists of the nodes.
    1.36      ///
    1.37 -    /// The type of the map that stores the dists of the nodes.
    1.38 -    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
    1.39 +    /// The type of the matrix map that stores the dists of the nodes.
    1.40 +    /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
    1.41      ///
    1.42 -    typedef NodeMatrixMap<Graph, Value> DistMap;
    1.43 -
    1.44 +    typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
    1.45 +    
    1.46      /// \brief Instantiates a DistMap.
    1.47      ///
    1.48      /// This function instantiates a \ref DistMap. 
    1.49 @@ -150,6 +151,15 @@
    1.50    /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
    1.51    /// kind of length.
    1.52    ///
    1.53 +  /// The algorithm solves the shortest path problem for each pairs
    1.54 +  /// of node when the edges can have negative length but the graph should
    1.55 +  /// not contain circle with negative sum of length. If we can assume
    1.56 +  /// that all edge is non-negative in the graph then the dijkstra algorithm
    1.57 +  /// should be used from each node.
    1.58 +  ///
    1.59 +  /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
    1.60 +  /// with fibonacci heap O(n^2 * log(n) + n * e).
    1.61 +  ///
    1.62    /// The type of the length is determined by the
    1.63    /// \ref concept::ReadMap::Value "Value" of the length map.
    1.64    ///