Changeset 1723:fb4f801dd692 in lemon0.x for lemon/johnson.h
 Timestamp:
 10/14/05 12:53:51 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2250
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/johnson.h
r1710 r1723 30 30 #include <lemon/error.h> 31 31 #include <lemon/maps.h> 32 #include <lemon/matrix_maps.h> 32 33 33 34 #include <limits> … … 107 108 typedef JohnsonDefaultOperationTraits<Value> OperationTraits; 108 109 109 /// \brief The type of the ma p that stores the last edges of the110 /// \brief The type of the matrix map that stores the last edges of the 110 111 /// shortest paths. 111 112 /// 112 /// The type of the map that stores the last 113 /// edges of the shortest paths. 113 /// The type of the map that stores the last edges of the shortest paths. 114 114 /// It must be a matrix map with \c Graph::Edge value type. 115 115 /// 116 typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap; 116 typedef DynamicMatrixMap<Graph, typename Graph::Node, 117 typename Graph::Edge> PredMap; 117 118 118 119 /// \brief Instantiates a PredMap. … … 125 126 } 126 127 127 /// \brief The type of the ma p that stores the dists of the nodes.128 /// 129 /// The type of the ma p that stores the dists of the nodes.130 /// It must meet the \ref concept::WriteMa p "WriteMap" concept.131 /// 132 typedef NodeMatrixMap<Graph, Value> DistMap;133 128 /// \brief The type of the matrix map that stores the dists of the nodes. 129 /// 130 /// The type of the matrix map that stores the dists of the nodes. 131 /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept. 132 /// 133 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap; 134 134 135 /// \brief Instantiates a DistMap. 135 136 /// … … 150 151 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 151 152 /// kind of length. 153 /// 154 /// The algorithm solves the shortest path problem for each pairs 155 /// of node when the edges can have negative length but the graph should 156 /// not contain circle with negative sum of length. If we can assume 157 /// that all edge is nonnegative in the graph then the dijkstra algorithm 158 /// should be used from each node. 159 /// 160 /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or 161 /// with fibonacci heap O(n^2 * log(n) + n * e). 152 162 /// 153 163 /// The type of the length is determined by the
Note: See TracChangeset
for help on using the changeset viewer.