Changeset 1270:806451fd084b in lemon0.x for src/lemon/min_cost_flow.h
 Timestamp:
 03/29/05 09:35:09 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1698
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/min_cost_flow.h
r1164 r1270 37 37 /// 38 38 /// 39 /// The class \ref lemon::MinCostFlow "MinCostFlow" implements 40 /// an algorithm for finding a flow of value \c k 41 /// having minimal total cost 42 /// from a given source node to a given target node in an 43 /// edgeweighted directed graph. To this end, 44 /// the edgecapacities and edgeweitghs have to be nonnegative. 45 /// The edgecapacities should be integers, but the edgeweights can be 46 /// integers, reals or of other comparable numeric type. 47 /// This algorithm is intended to use only for small values of \c k, 48 /// since it is only polynomial in k, 49 /// not in the length of k (which is log k). 50 /// In order to find the minimum cost flow of value \c k it 51 /// finds the minimum cost flow of value \c i for every 52 /// \c i between 0 and \c k. 39 /// The class \ref lemon::MinCostFlow "MinCostFlow" implements an 40 /// algorithm for finding a flow of value \c k having minimal total 41 /// cost from a given source node to a given target node in an 42 /// edgeweighted directed graph. To this end, the edgecapacities 43 /// and edgeweights have to be nonnegative. The edgecapacities 44 /// should be integers, but the edgeweights can be integers, reals 45 /// or of other comparable numeric type. This algorithm is intended 46 /// to be used only for small values of \c k, since it is only 47 /// polynomial in k, not in the length of k (which is log k): in 48 /// order to find the minimum cost flow of value \c k it finds the 49 /// minimum cost flow of value \c i for every \c i between 0 and \c 50 /// k. 53 51 /// 54 52 ///\param Graph The directed graph type the algorithm runs on. … … 150 148 potential.set(n, potential[n]+dijkstra.distMap()[n]); 151 149 152 //Augmenting on the s ortest path150 //Augmenting on the shortest path 153 151 Node n=t; 154 152 ResGraphEdge e; … … 227 225 228 226 This function checks, whether the given flow and potential 229 satisf iy the complementary slackness cnditions (i.e. these are optimal).227 satisfy the complementary slackness conditions (i.e. these are optimal). 230 228 This function only checks optimality, doesn't bother with feasibility. 231 229 For testing purpose.
Note: See TracChangeset
for help on using the changeset viewer.