Changeset 893:89d5c283a485 in lemon-0.x
- Timestamp:
- 09/21/04 23:10:26 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1201
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/mincostflows.h
r860 r893 24 24 /// The class \ref hugo::MinCostFlows "MinCostFlows" implements 25 25 /// an algorithm for finding a flow of value \c k 26 /// having minimal total cost 26 /// having minimal total cost 27 27 /// from a given source node to a given target node in an 28 /// edge-weighted directed graph having nonnegative integer capacities. 29 /// The range of the length (weight or cost) function can be nonnegative reals but 30 /// the range of the capacity function has to be the set of nonnegative integers. 31 /// This algorithm is intended to use only for for small values of \c k, since /// it is not a polinomial time algorithm for finding the minimum cost 32 /// maximal flow (in order to find the minimum cost flow of value \c k it 28 /// edge-weighted directed graph. To this end, 29 /// the edge-capacities and edge-weitghs have to be nonnegative. 30 /// The edge-capacities should be integers, but the edge-weights can be 31 /// integers, reals or of other comparable numeric type. 32 /// This algorithm is intended to use only for small values of \c k, 33 /// since it is only polynomial in k, 34 /// not in the length of k (which is log k). 35 /// In order to find the minimum cost flow of value \c k it 33 36 /// finds the minimum cost flow of value \c i for every 34 /// \c i between 0 and \c k ).37 /// \c i between 0 and \c k. 35 38 /// 36 39 ///\param Graph The directed graph type the algorithm runs on. … … 41 44 template <typename Graph, typename LengthMap, typename CapacityMap> 42 45 class MinCostFlows { 43 44 45 46 46 47 typedef typename LengthMap::ValueType Length;
Note: See TracChangeset
for help on using the changeset viewer.