Changeset 1723:fb4f801dd692 in lemon-0.x for lemon/floyd_warshall.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/floyd_warshall.h
r1710 r1723 28 28 #include <lemon/invalid.h> 29 29 #include <lemon/error.h> 30 #include <lemon/matrix_maps.h> 30 31 #include <lemon/maps.h> 31 32 … … 106 107 typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits; 107 108 108 /// \brief The type of the ma p that stores the last edges of the109 /// \brief The type of the matrix map that stores the last edges of the 109 110 /// shortest paths. 110 111 /// 111 /// The type of the map that stores the last 112 /// edges of the shortest paths. 112 /// The type of the map that stores the last edges of the shortest paths. 113 113 /// It must be a matrix map with \c Graph::Edge value type. 114 114 /// 115 typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap; 115 typedef DynamicMatrixMap<Graph, typename Graph::Node, 116 typename Graph::Edge> PredMap; 116 117 117 118 /// \brief Instantiates a PredMap. … … 127 128 /// 128 129 /// The type of the map that stores the dists of the nodes. 129 /// It must meet the \ref concept::WriteMa p "WriteMap" concept.130 /// 131 typedef NodeMatrixMap<Graph, Value> DistMap;130 /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept. 131 /// 132 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap; 132 133 133 134 /// \brief Instantiates a DistMap. … … 149 150 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 150 151 /// kind of length. 152 /// 153 /// The algorithm solves the shortest path problem for each pairs 154 /// of node when the edges can have negative length but the graph should 155 /// not contain circle with negative sum of length. If we can assume 156 /// that all edge is non-negative in the graph then the dijkstra algorithm 157 /// should be used from each node rather and if the graph is sparse and 158 /// there are negative circles then the johson algorithm. 159 /// 160 /// The complexity of this algorithm is O(n^3 + e). 151 161 /// 152 162 /// The type of the length is determined by the
Note: See TracChangeset
for help on using the changeset viewer.