Changeset 1723:fb4f801dd692 in lemon-0.x for lemon/johnson.h
- Timestamp:
- 10/14/05 12:53:51 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/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 non-negative 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.